一 時間復(fù)雜度
1.1 度量一個程序(算法)執(zhí)行時間的兩種方法
- 事后統(tǒng)計的方法 這種方法可行, 但是有兩個問題：一是要想對設(shè)計的算法的運行性能進行評測，需要
實際運行該程序；二是所得時間的統(tǒng)計量依賴于計算機的硬件、軟件等環(huán)境因素, 這種方式，要在同一臺計算機的相同狀態(tài)下運行，才能比較那個算法速度更快。 - 事前
估算的方法 通過分析某個算法的時間復(fù)雜度來判斷哪個算法更優(yōu).
1.2 時間頻度
一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T(n)
總結(jié)
- 時間復(fù)雜度中，
常數(shù)項可以忽略 -
低次項可以忽略
image.png
1.3 時間復(fù)雜度
- 一般情況下，算法中的基本操作語句的重復(fù)執(zhí)行次數(shù)是問題規(guī)模 n 的某個函數(shù)，用 T(n)表示，若有某個輔助函數(shù) f(n)，使得當 n 趨近于無窮大時，T(n) / f(n) 的極限值為不等于零的常數(shù)，則稱 f(n)是 T(n)的
同數(shù)量級函數(shù)。 記作T(n)=Ｏ( f(n) )，稱Ｏ( f(n) ) 為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。 -
T(n) 不同，但時間復(fù)雜度可能相同。 如：T(n)=n2+7n+6 與 T(n)=3n2+2n+2 它們的 T(n) 不同，但時間復(fù)雜 度相同，都為 O(n2)。 - 計算時間復(fù)雜度的方法：
- 用常數(shù) 1 代替運行時間中的所有加法常數(shù) T(n)=n2+7n+6 => T(n)=n2+7n+1
- 修改后的運行次數(shù)函數(shù)中，只保留最高階項 T(n)=n2+7n+1 => T(n) = n2
- 去除最高階項的系數(shù) T(n) = n2 => T(n) = n2 => O(n2)
1.4 常見的時間復(fù)雜度
- 常數(shù)階 O(1)
- 對數(shù)階 O(log2n)
- 線性階 O(n)
- 線性對數(shù)階 O(nlog2n)
- 平方階 O(n^2)
- 立方階 O(n^3)
- k 次方階 O(n^k)
- 指數(shù)階 O(2^n)
二 空間復(fù)雜度
- 類似于時間復(fù)雜度的討論，一個算法的空間復(fù)雜度(Space Complexity)定義為該算法
所耗費的存儲空間，它也是 問題規(guī)模 n 的函數(shù)。 - 空間復(fù)雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。有的算法需要占用的臨時工作單元數(shù)與解決問題的規(guī)模 n 有關(guān)，它隨著 n 的增大而增大，當 n 較大時，將占用較多的存儲單元，例 如快速排序和歸并排序算法, 基數(shù)排序就屬于這種情況
- 在做算法分析時，
主要討論的是時間復(fù)雜度。從用戶使用體驗上看，更看重的程序執(zhí)行的速度。一些緩存產(chǎn)品 (redis, memcache)和算法(基數(shù)排序)本質(zhì)就是用空間換時間.
