數據結構之複雜度
複雜度
綱要：
- 演算法效率
- 時間複雜度
- 概念
- 大O的漸進表示法
- 示例
- 空間複雜度
- 概念
- 示例
在我們學習完C語言之後，我們就要蹦著向更高處走了，所以今天，我們來到了數據結構。
下面呢，就正式開啟數據結構的大門！
一.演算法效率
演算法效率分析分為兩種：
1.時間效率
時間效率又叫做時間複雜度，它衡量的主要是一個演算法的運行速度。
2.空間效率
空間效率又叫做空間複雜度，它衡量的主要是一個演算法所需要的額外空間。在電腦發展的早期，因為科技水平有限，往往電腦的容量很少，但如今科技急速發展，電腦的存儲容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個演算法的空間複雜度。
二.時間複雜度
1.概念
在電腦科學中，演算法的時間複雜度是一個函數，它定量描述了該演算法的運行時間。一 個演算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道。但是我們需要每個演算法都上機測試嗎？是可以都上機測試，但是同一個演算法在不同性能的機器上也會有不同的差異，所以才有了時間複雜度這個分析方式。
因一個演算法所花費的時間與其中語句的執行次數成正比例，所以，演算法中的基本操作的執行次數，為演算法的時間複雜度。
比如所如下程式碼，它的執行次數為多少呢？
#include <stdio.h> void Func1(int N) { int count = 0; for (int i = 0; i < N ; ++ i) { for (int j = 0; j < N ; ++ j) { ++count; } } for (int k = 0; k < 2 * N ; ++ k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count); }
顯而易見，它的執行次數為 F=N*N+2*N+10；
往往我們在計算時間複雜度的時候，我們寫的是一個概數，為什麼呢？
我們不妨設想一下，對於上面的執行次數函數，當N趨向於無窮大時，那個10對於它的影響微乎其微。如果是一個高階函數，這個函數的大小往往取決於表達式中次數最高的項，所以我們的時間複雜度也採取這種思想。
我們不妨來測試一下：
#include <stdio.h> #include <time.h> void Func1(int N) { int start = clock(); int count = 0; for (int i = 0; i < N ; ++ i) { for (int j = 0; j < N ; ++ j) { ++count; } } for (int k = 0; k < 2 * N ; ++ k) { ++count; } int M = 10; while (M--) { ++count; } int end = clock(); printf("%d\n", end - start);//單位為毫秒 } int main() { Func1(0);//0 Func1(100);//0 Func1(10000);//386 return 0; }
我們發現，差異主要是在最高次上面。所以接下來我們來介紹大O的漸進表示法。
2.大O的漸進表示法
實際中我們計算時間複雜度時，我們其實並不一定要計算精確的執行次數，而只需要大概執行次數，那麼這裡我們使用大O的漸進表示法。
大O符號（Big O notation）：是用於描述函數漸進行為的數學符號。
推導大O階方法：
1、用常數1取代運行時間中的所有加法常數。
2、在修改後的運行次數函數中，只保留最高階項。
3、如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大O階。
所以，使用大O的漸進表示法以後，Func1的時間複雜度為：O(N^2);
通過上面，我們可以得到現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數。
另外有些演算法的時間複雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數(下界)
例如：
//描述：傳遞一個數組，給定一個數，查找該數組中是否含有這個數 int FindNum(int* arr,int N,int search_num) { int i = 0; for(i=0;i<len;i++) { if(search_num == arr[i]) return 1;//找到則返回 1 } return 0;//找不到則返回 0 }
它的最好情況為 1 ，即只執行一次就找到了
平均情況：N/2
最差情況： N ，遍歷了整個數組。
那麼，對於這個演算法，它的時間複雜度是多少呢？答案是: O(N)
在計算時間複雜度時，我們往往取得是它的最差情況。
3.示例
// 1.計算Func2的時間複雜度？ void Func2(int N) { int count = 0; for (int k = 0; k < 2 * N ; ++ k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count); }
它的時間複雜度為多少呢？ —- O(N)
// 2.計算Func3的時間複雜度？ void Func3(int N, int M) { int count = 0; for (int k = 0; k < M; ++ k) { ++count; } for (int k = 0; k < N ; ++ k) { ++count; } printf("%d\n", count); }
答案是：O(N+M) ，因為在這個式子中，我們並不知道M和N的大小情況，如果N>>M，那這題的時間複雜度就是O(N)
//3. 計算Func4的時間複雜度？ void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++ k) { ++count; } printf("%d\n", count); }
對於它，執行次數為一個確定的常數：100，所以它的時間複雜度為 O(1)
// 4.計算BubbleSort的時間複雜度？ void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }
對於實例4基本操作執行最好N次，最壞執行了(N*(N+1)/2次，通過推導大O階方法+時間複雜度一般看最壞，所以時間複雜度為 O(N^2)
// 5.計算BinarySearch的時間複雜度？ int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n-1; while (begin < end) { int mid = begin + ((end-begin)>>1); if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid; else return mid; } return -1; }
實例5基本操作執行最好1次，最壞O(logN)次，時間複雜度為 O(logN)（我們可以通過摺紙查找的方式理解logN是怎麼計算出來的）
註：
logN在演算法分析中表示是底數為2，對數為N。有些地方會寫成lgN。
// 6.計算階乘遞歸Factorial的時間複雜度？ long long Factorial(size_t N) { return N < 2 ? N : Factorial(N-1)*N; }
對於遞歸的時間複雜度我們怎麼算呢？
遞歸的時間複雜度 = 遞歸次數*每次遞歸中的次數
對於上題，一共遞歸了N次，每次遞歸中只有一次，所以時間複雜度為O(N)
//7. 計算斐波那契遞歸Fibonacci的時間複雜度？ long long Fibonacci(size_t N) { return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2); }
在這個例中，一共遞歸了N次，而在遞歸中的次數為2^N-1,所以最後的時間複雜度為：O(N^2)
註：
如果有一個遞歸有N層，且每一層中又有N次，那麼它最後的時間複雜度為 O(N^2）
三.空間複雜度
1.概念
空間複雜度是對一個演算法在運行過程中臨時佔用存儲空間大小的量度 。空間複雜度不是程式佔用了多少 bytes的空間，因為這個也沒太大意義，
所以空間複雜度算的是變數的個數。
空間複雜度計算規則基本跟實踐 複雜度類似，也使用大O漸進表示法。（估算）
2.示例
//1. 計算BubbleSort的空間複雜度？ void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }
我們要注意在計算時，我們計算的是演算法需要的額外空間，不考慮數組輸入的空間。並且我們要注意，空間是可以復用的，比如所某個演算法需要創建一個變數並不斷的為這個變數賦值，這時這個空間複雜度為O(1);
所以，因實例1使用了常數個額外空間，所以空間複雜度為 O(1)
//2. 計算生成的Fibonacci數組的空間複雜度？ long long* Fibonacci(size_t n) { if(n==0) { return NULL; } long long * fibArray = (long long *)malloc((n+1) * sizeof(long long)); fibArray[0] = 0;//斐波那契數的第一個 fibArray[1] = 1;//斐波那契數的第二個 for (int i = 2; i <= n ; ++i)//利用循環來生成斐波那契數 { fibArray[i ] = fibArray[ i - 1] + fibArray [i - 2]; } return fibArray ; }
實例 2動態開闢了N個空間來放N個斐波那契數，所以空間複雜度為 O(N)
//3. 計算階乘遞歸Factorial的空間複雜度？ long long Factorial(size_t N) { return N < 2 ? N : Factorial(N-1)*N; }
遞歸演算法的空間複雜度通常情況下為 遞歸的深度 (遞歸的次數)
實例3遞歸調用了N次，開闢了N個棧幀，每個棧幀使用了常數個空間。所以空間複雜度為O(N).
那麼在最後我們再來看一張圖：
這就說明有時候 不同的時間複雜度在N小的時候都還接近，當N越來越大時差距越來越多！
|——————————————————–
關於複雜度的知識到這便結束了
因筆者水平有限，若有錯誤，還望指正
