衡量一個演算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度
時間復雜度
1）概念
演算法的時間復雜度是一個函式 ，演算法中的基本操作的執行次數，為演算法的時間復雜度
2）大O的漸進表示法
大O符號（Big O notation）
方法：
- 用常數1取代運行時間中的所有加法常數，
- 在修改后的運行次數函式中，只保留最高階項，
- 如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階，
當O(M+N)時可寫為O(max(M,N)):
- 當M遠大于N時記作O(M)
- 當N遠大于M時記作O(N)
例如：
N^2+2*N+10的時間復雜度為：2N
3）最好、平均和最壞情況
最好情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最壞情況：任意輸入規模的最小運行次數(下界)
例：
在一個長度為N陣列中搜索一個資料n
最好情況：1次
平均情況：N/2次
最壞情況：N次
4）例題
1.
計算Func4的時間復雜度void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++ k) { ++count; } printf("%d\n", count); }
分析：用方法一，常數次為O(1)
2.
計算階乘遞回Fac的時間復雜度long long Fac(size_t N) { if(1 == N) return 1; return Fac(N-1)*N; }遞回演算法的時間復雜度計算：
遞回次數N乘以每次遞回呼叫中的次數
分析：
- 每次遞回呼叫中只有一個return 1，為一
- 從N，N-1，N-2，…，1一共N次
所以階乘遞回Fac的時間復雜度O(N*1)=O(N)
3.
計算斐波那契遞回Fib的時間復雜度long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
分析如上圖：共需2^0+2^1+2^2+...+2^(N-2)次,用等比數列算出為2^(N-1)-1次，用大O的漸進表示法表示為O(2^N)
4.
計算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; }
分析如圖：最后N/2/2/2/2.../2=1設有x個2則N=2^x，x=log(N)/log(2)，用大O的漸進表示法表示為O(logN)
基本操作執行最好1次，最壞O(logN)次，時間復雜度為 O(logN)
空間復雜度
1）概念
- 空間復雜度是一個數學運算式，是對一個演算法在運行程序中臨時占用存盤空間大小的量度
時間累計，空間不累計
2）例題
1.
計算階乘遞回Fac的空間復雜度long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }
分析：遞回呼叫了N次，開辟了N個堆疊幀，每個堆疊幀使用了常數個空間，空間復雜度為O(N)
2.
計算斐波那契遞回Fib的空間復雜度long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
分析如圖：每呼叫一次遞回會占用空間呼叫完后會銷毀空間再進行下一次遞回，如此實際只占用了N個空間，空間復雜度為O(N)
時間累計，空間不累計
常見復雜度
| 5201314 | O(1) | 常數階 |
|---|---|---|
| 3n+4 | O(n) | 線性階 |
| 3n^2+4n+5 | O(n^2) | 平方階 |
| 3log(2)n+4 | O(logn) | 對數階（速度和常數階相差不大） |
| 2n+ 3nlog(2)n+14 | O(nlogn) | nlogn階 |
| n^3+2n^2+4n+6 | O(n^3) | 立方階 |
| 2^n | O(2^n) | 指數階 |
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/291032.html
標籤：其他
上一篇：TCP和UDP