記錄資料結構的學習——復雜度
- 時間復雜度
- 優化
- 增長率
- 空間復雜度
- 化簡
- O(n)的化簡
課本中并沒有復雜度的概念，我將時間復雜度和空間復雜度合并簡稱為復雜度，若有不對還希望大家指點出來，謝謝！
時間復雜度
演算法中基本操作重復執行次數稱為陳述句頻度，記為T(n)，
我們寫的代碼中常會出現不同的時間復雜度，時間復雜度越大，我們的程式效率便越低，例如某著名游戲聯機版加載時間短則3、4分鐘，長則10+分鐘，這背后的原因既不是道德的淪喪，也不是人性的扭曲，而是爛代碼中的一條if陳述句回圈了19.8億次，
在求和函式中while(–n)執行了n次，時間復雜度為O(n)
int Sum(int n)
{
int sum = n;
while(--n)
{
sum += n;
}
return sum;
}
優化
可優化為
int Sum(int n)
{
int sum = n++ * n / 2;
return sum;
}
此時由于只執行了一次( n++ * n / 2)， 所以時間復雜度為O(1)，
增長率
當輸入規模增加時，時間復雜度增加的速度
| n | log(2, n) | 0.5n | 2n | n * log(2, n) | n ^ 2 | 2 ^ n | n! |
|---|---|---|---|---|---|---|---|
| 2 | 1 | 1 | 4 | 2 | 4 | 4 | 2 |
| 4 | 2 | 2 | 8 | 8 | 16 | 16 | 24 |
| 8 | 3 | 4 | 16 | 24 | 64 | 512 | 40320 |
| 16 | 4 | 8 | 32 | 64 | 256 | 65336 | … |
| 32 | 5 | 16 | 64 | 160 | 1024 | … | … |
| 64 | 6 | 32 | 128 | 384 | 4096 | … | … |
| 128 | 7 | 64 | 256 | 896 | 16384 | … | … |
| 256 | 8 | 128 | 512 | 2048 | 65336 | … | … |
| 512 | 9 | 256 | 1024 | 4608 | … | … | … |
| 1024 | 10 | 512 | 2048 | 10240 | … | … | … |
由上表我們不能否認一個結論，那就是好的時間復雜度的演算法可以提高很多效率，
空間復雜度
完成演算法所需空間的度量，//額外空間
在此求和函式中
int Sum(int n)
{
int sum = n;
if (--n)
{
sum += Sum(n);
}
return sum;
}
雖只用了一個變數sum，但進行了n次遞回呼叫，所以空間復雜度為O(n)，
化簡
int Sum(int n)
{
int sum = n++ * n / 2;
return sum;
}
在這個求和函式中，只用了一個變數sum，所以空間復雜度為O(1)，
O(n)的化簡
1、若T(n)在O(g(n))中，g(n)在O(h(n))中，則T(n)在O(n)中，
2、對于任意的正常數k，若T(n)在O(k * g(n))中， 則T(n)在O(g(n))中，//系數不影響時間復雜度
3、若T1(n)在O(g1(n))中，T2(n)在O(g2(n))中，則T1(n) + T2(n)在O(Max(g1(n), g2(n)))中，//加法中考慮增加速度最快的一條曲線，
4、若T1(n)在O(g1(n))中，T2(n)在O(g2(n))中，則T1(n) * T2(n)在O(g1(n) * g2(n))中，//乘法中考慮嵌套的代碼，
例如 T(n) = 3n ^ 2 + 4n + 5，
由2知 令 k = 1 , T(n) 在O(3n ^ 2 + 4n + 5)中，可看做T(n + 0 + 0)在O(3n ^ 2 + 4n + 5)，
由3知 T(n) 在O(Max(3n ^ 2 , 4n, 5))中，顯然當n較大時，Max(3n ^ 2 , 4n, 5)為3n ^ 2，則T(n)在O(3n^2)中，
由2知 3n^ 2 在 O(n ^ 2) 中，
由1知 T(n) 在 O(n ^ 2) 中，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/272276.html
標籤：其他
上一篇：函式發生器課程設計（Multisim仿真+PCB實物）
下一篇：C語言檔案操作