在分析演算法效率時，經常關注以下兩種復雜度：
（1）最壞情況復雜度：Tworst(n)
（2）平均復雜度：Tavg(n)
易知Tavg(n)<=Tworst(n)
注：一般分析最壞情況復雜度，因為平均復雜度不容易找
下表能夠比較直觀的看出各個復雜度的運行時間
| 1 | 2 | 4 | 8 | 16 | 32 | |
| C（常函式） | 1 | 1 | 1 | 1 | 1 | 1 |
| logn | 0 | 1 | 2 | 3 | 4 | 5 |
| n | 1 | 2 | 4 | 8 | 16 | 32 |
| nlogn | 0 | 2 | 8 | 24 | 64 | 160 |
| n2 | 1 | 4 | 16 | 64 | 256 | 1024 |
| n3 | 1 | 8 | 64 | 512 | 4096 | 32768 |
| 2n | 2 | 4 | 16 | 256 | 65536 | 4294967296 |
| n! | 1 | 2 | 24 | 40326 | 2092278988000 | 26313×1033 |
所以一般情況下避免出現后兩種復雜度
下圖是幾種復雜度的增長速度
（圖片來自慕課，陳越姥姥那堂課）
復雜度分析的竅門：
- 若已知T1(n) = O(f1(n))和T2(n) = O(f2(n))，則
T1(n) + T2(n) = max(O(f1(n)),O(f2(n))) （就是O(f1(n))和O(f2(n))的最大值）
T1(n) × T2(n) = O(f1(n) × f2(n)) - for回圈的T(n) = 回圈次數 × 回圈體代碼的復雜度
- if-else結構的復雜度取決于if的條件判斷復雜度和兩個分支部分的復雜度，總體復雜度取三者中的最大值
2020-03-19
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/71873.html
標籤：其他