演演算法(Algorithm)是指用來運算元據、解決程式問題的一組方法。對於同一個問題,使用不同的演演算法,也許最終得到的結果是一樣的,比如排序就有前面的十大經典排序和幾種奇葩排序,雖然結果相同,但在過程中消耗的資源和時間卻會有很大的區別,比如快速排序與猴子排序:)。
如果你想要了解更多複雜度相關的知識,可以看看我之前的文章
「時間」與「空間」複雜度
更多演演算法內容請存取:五分鐘學演演算法
那麼我們應該如何去衡量不同演演算法之間的優劣呢?
主要還是從演演算法所佔用的「時間」和「空間」兩個維度去考量。
時間的流逝宛若寒冰的融化,散發著恐懼。
大O表示法:演演算法的時間複雜度通常用大O符號表述,定義為 **T[n] = O(f(n)) **。稱函數T(n)以f(n)為界或者稱T(n)受限於f(n)。
如果一個問題的規模是n,解這一問題的某一演演算法所需要的時間為T(n)。T(n)稱為這一演演算法的「時間複雜度」。
上面公式中用到的 Landau符號是由德國數論學家保羅·巴赫曼(Paul Bachmann)在其1892年的著作《解析數論》首先引入,由另一位德國數論學家艾德蒙·朗道(Edmund Landau)推廣。Landau符號的作用在於用簡單的函數來描述複雜函數行為,給出一個上或下(確)界。在計算演演算法複雜度時一般只用到大O符號,Landau符號體系中的小o符號、Θ符號等等比較不常用。這裡的O,最初是用大寫希臘字母,但現在都用大寫英語字母O;小o符號也是用小寫英語字母o,Θ符號則維持大寫希臘字母Θ。
大O符號是一種演演算法「複雜度」的「相對」「表示」方式。
這個句子裡有一些重要而嚴謹的用詞:
我們先從常見的時間複雜度量級進行大O的理解:
無論程式碼執行了多少行,其他區域不會影響到操作,這個程式碼的時間複雜度都是O(1)
void swapTwoInts(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
在下面這段程式碼,for迴圈裡面的程式碼會執行 n 遍,因此它消耗的時間是隨著 n 的變化而變化的,因此可以用O(n)來表示它的時間複雜度。
int sum ( int n ){
int ret = 0;
for ( int i = 0 ; i <= n ; i ++){
ret += i;
}
return ret;
}
特別一提的是 c * O(n) 中的 c 可能小於 1 ,比如下面這段程式碼:
void reverse ( string &s ) {
int n = s.size();
for (int i = 0 ; i < n/2 ; i++){
swap ( s[i] , s[n-1-i]);
}
}
void selectionSort(int arr[],int n){
for(int i = 0; i < n ; i++){
int minIndex = i;
for (int j = i + 1; j < n ; j++ )
if (arr[j] < arr[minIndex])
minIndex = j;
swap ( arr[i], arr[minIndex]);
}
}
這裡簡單的推導一下
不難得到公式:
(n - 1) + (n - 2) + (n - 3) + ... + 0
= (0 + n - 1) * n / 2
= O (n ^2)
當然並不是所有的雙重回圈都是 O(n²),比如下面這段輸出 30n 次 Hello,五分鐘學演演算法:)
的程式碼。
void printInformation (int n ){
for (int i = 1 ; i <= n ; i++)
for (int j = 1 ; j <= 30 ; j ++)
cout<< "Hello,五分鐘學演演算法:)"<< endl;
}
int binarySearch( int arr[], int n , int target){
int l = 0, r = n - 1;
while ( l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] > target ) r = mid - 1;
else l = mid + 1;
}
return -1;
}
在二分查詢法的程式碼中,通過while迴圈,成 2 倍數的縮減搜尋範圍,也就是說需要經過 log2^n 次即可跳出迴圈。
同樣的還有下面兩段程式碼也是 O(logn) 級別的時間複雜度。
// 整形轉成字串
string intToString ( int num ){
string s = "";
// n 經過幾次「除以10」的操作後,等於0
while (num ){
s += '0' + num%10;
num /= 10;
}
reverse(s)
return s;
}
void hello (int n ) {
// n 除以幾次 2 到 1
for ( int sz = 1; sz < n ; sz += sz)
for (int i = 1; i < n; i++)
cout<< "Hello,五分鐘學演演算法:)"<< endl;
}
將時間複雜度為O(logn)的程式碼迴圈N遍的話,那麼它的時間複雜度就是 n * O(logn),也就是了O(nlogn)。
void hello (){
for( m = 1 ; m < n ; m++){
i = 1;
while( i < n ){
i = i * 2;
}
}
}
下面來分析一波另外幾種複雜度: 遞迴演演算法的時間複雜度(recursive algorithm time complexity),最好情況時間複雜度(best case time complexity)、最壞情況時間複雜度(worst case time complexity)、平均時間複雜度(average case time complexity)和均攤時間複雜度(amortized time complexity)。
如果遞迴函數中,只進行一次遞迴呼叫,遞迴深度為depth;
在每個遞迴的函數中,時間複雜度為T;
則總體的時間複雜度為O(T * depth)。
在前面的學習中,歸併排序 與 快速排序 都帶有遞迴的思想,並且時間複雜度都是O(nlogn) ,但並不是有遞迴的函數就一定是 O(nlogn) 級別的。從以下兩種情況進行分析。
int binarySearch(int arr[], int l, int r, int target){
if( l > r ) return -1;
int mid = l + (r-l)/2;
if( arr[mid] == target ) return mid;
else if( arr[mid] > target )
return binarySearch(arr, l, mid-1, target); // 左邊
else
return binarySearch(arr, mid+1, r, target); // 右邊
}
比如在這段二分查詢法的程式碼中,每次在 [ l , r ] 範圍中去查詢目標的位置,如果中間的元素 arr[mid]
不是 target
,那麼判斷 arr[mid]
是比 target
大 還是 小 ,進而再次呼叫 binarySearch
這個函數。
在這個遞迴函數中,每一次沒有找到target
時,要麼呼叫 左邊 的 binarySearch
函數,要麼呼叫 右邊 的 binarySearch
函數。也就是說在此次遞迴中,最多呼叫了一次遞迴呼叫而已。根據數學知識,需要log2n次才能遞迴到底。因此,二分查詢法的時間複雜度為 O(logn)。
int sum (int n) {
if (n == 0) return 0;
return n + sum( n - 1 )
}
在這段程式碼中比較容易理解遞迴深度隨輸入 n 的增加而線性遞增,因此時間複雜度為 O (n)。
//遞迴深度:logn
//時間複雜度:O(logn)
double pow( double x, int n){
if (n == 0) return 1.0;
double t = pow(x,n/2);
if (n %2) return x*t*t;
return t * t;
}
遞迴深度為 logn
,因為是求需要除以 2 多少次才能到底。
遞迴演演算法中比較難計算的是多次遞迴呼叫。
先看下面這段程式碼,有兩次遞迴呼叫。
// O(2^n) 指數級別的數量級,後續動態規劃的優化點
int f(int n){
if (n == 0) return 1;
return f(n-1) + f(n - 1);
}
遞迴樹中節點數就是程式碼計算的呼叫次數。
比如 當 n = 3
時,呼叫次數計算公式為
1 + 2 + 4 + 8 = 15
一般的,呼叫次數計算公式為
2^0 + 2^1 + 2^2 + …… + 2^n
= 2^(n+1) - 1
= O(2^n)
與之有所類似的是 歸併排序 的遞迴樹,區別點在於
n
,而 歸併排序 的遞迴樹深度為logn
。因此,在如 歸併排序 等排序演演算法中,每一層處理的資料量為 O(n) 級別,同時有 logn
層,時間複雜度便是 O(nlogn)。
動圖表明的是在陣列 array 中尋找變數 x 第一次出現的位置,若沒有找到,則返回 -1;否則返回位置下標。
int find(int[] array, int n, int x) {
for ( int i = 0 ; i < n; i++) {
if (array[i] == x) {
return i;
break;
}
}
return -1;
}
在這裡當陣列中第一個元素就是要找的 x 時,時間複雜度是 O(1);而當最後一個元素才是 x 時,時間複雜度則是 O(n)。
最好情況時間複雜度就是在最理想情況下執行程式碼的時間複雜度,它的時間是最短的;最壞情況時間複雜度就是在最糟糕情況下執行程式碼的時間複雜度,它的時間是最長的。
最好、最壞時間複雜度反應的是極端條件下的複雜度,發生的概率不大,不能代表平均水平。那麼為了更好的表示平均情況下的演演算法複雜度,就需要引入平均時間複雜度。
平均情況時間複雜度可用程式碼在所有可能情況下執行次數的加權平均值表示。
還是以 find
函數為例,從概率的角度看, x 在陣列中每一個位置的可能性是相同的,為 1 / n。那麼,那麼平均情況時間複雜度就可以用下面的方式計算:
((1 + 2 + … + n) / n + n) / 2 = (3n + 1) / 4
find
函數的平均時間複雜度為 O(n)。
我們通過一個動態陣列的 push_back
操作來理解 均攤複雜度。
template <typename T>
class MyVector{
private:
T* data;
int size; // 儲存陣列中的元素個數
int capacity; // 儲存陣列中可以容納的最大的元素個數
// 複雜度為 O(n)
void resize(int newCapacity){
T *newData = new T[newCapacity];
for( int i = 0 ; i < size ; i ++ ){
newData[i] = data[i];
}
data = newData;
capacity = newCapacity;
}
public:
MyVector(){
data = new T[100];
size = 0;
capacity = 100;
}
// 平均複雜度為 O(1)
void push_back(T e){
if(size == capacity)
resize(2 * capacity);
data[size++] = e;
}
// 平均複雜度為 O(1)
T pop_back(){
size --;
return data[size];
}
};
push_back
實現的功能是往陣列的末尾增加一個元素,如果陣列沒有滿,直接往後面插入元素;如果陣列滿了,即 size == capacity
,則將陣列擴容一倍,然後再插入元素。
例如,陣列長度為 n,則前 n 次呼叫 push_back
複雜度都為 O(1) 級別;在第 n + 1 次則需要先進行 n 次元素轉移操作,然後再進行 1 次插入操作,複雜度為 O(n)。
因此,平均來看:對於容量為 n 的動態陣列,前面新增元素需要消耗了 1 * n 的時間,擴容操作消耗 n 時間 ,
總共就是 2 * n 的時間,因此均攤時間複雜度為 O(2n / n) = O(2),也就是 O(1) 級別了。
可以得出一個比較有意思的結論:一個相對比較耗時的操作,如果能保證它不會每次都被觸發,那麼這個相對比較耗時的操作,它所相應的時間是可以分攤到其它的操作中來的。
🔥🔥🔥🔥,到處都是🔥
一個程式的空間複雜度是指執行完一個程式所需記憶體的大小。利用程式的空間複雜度,可以對程式的執行所需要的記憶體多少有個預先估計。一個程式執行時除了需要儲存空間和儲存本身所使用的指令、常數、變數和輸入資料外,還需要一些對資料進行操作的工作單元和儲存一些為現實計算所需資訊的輔助空間。程式執行時所需儲存空間包括以下兩部分:
(1) 固定部分,這部分空間的大小與輸入/輸出的資料的個數多少、數值無關。主要包括指令空間(即程式碼空間)、資料空間(常數、簡單變數)等所佔的空間。這部分屬於靜態空間。
(2) 可變空間,這部分空間的主要包括動態分配的空間,以及遞迴棧所需的空間等。這部分的空間大小與演演算法有關。
一個演演算法所需的儲存空間用f(n)表示。S(n)=O(f(n)),其中n為問題的規模,S(n)表示空間複雜度。
空間複雜度可以理解為除了原始序列大小的記憶體,在演演算法過程中用到的額外的儲存空間。
以二叉查詢樹為例,舉例說明二叉排序樹的查詢效能。
如果二元樹的是以紅黑樹等平衡二元樹實現的,則 n 個節點的二叉排序樹的高度為 log2n+1 ,其查詢效率為O(Log2n),近似於折半查詢。
如果二元樹退變為列表了,則 n 個節點的高度或者說是長度變為了n,查詢效率為O(n),變成了順序查詢。
介於「列表二元樹」與「平衡二元樹」之間,查詢效能也在O(Log2n)到O(n)之間。
對於一個演演算法,其時間複雜度和空間複雜度往往是相互影響的。
比如說,要判斷某某年是不是閏年:
這就是典型的使用空間換時間的概念。
當追求一個較好的時間複雜度時,可能會使空間複雜度的效能變差,即可能導致佔用較多的儲存空間;
反之,求一個較好的空間複雜度時,可能會使時間複雜度的效能變差,即可能導致佔用較長的執行時間。
另外,演演算法的所有效能之間都存在著或多或少的相互影響。因此,當設計一個演演算法(特別是大型演演算法)時,要綜合考慮演演算法的各項效能,演演算法的使用頻率,演演算法處理的資料量的大小,演演算法描述語言的特性,演演算法執行的機器系統環境等各方面因素,才能夠設計出比較好的演演算法。
更多演演算法內容請存取:五分鐘學演演算法