目錄

?

為什么需要復(fù)雜度分析？

大 O 復(fù)雜度表示法

時間復(fù)雜度分析

幾種常見時間復(fù)雜度

空間復(fù)雜度分析

---

為什么需要復(fù)雜度分析？

事后統(tǒng)計法：代碼跑一遍，通過統(tǒng)計、監(jiān)控，就能得到算法執(zhí)行的時間和占用的內(nèi)存大小。這種統(tǒng)計方法有非常大的局限性。

測試結(jié)果非常依賴測試環(huán)境

測試結(jié)果受數(shù)據(jù)規(guī)模的影響很大

因此，我們需要一個不用具體的測試數(shù)據(jù)來測試，就可以粗略地估計算法的執(zhí)行效率的方法。

大 O 復(fù)雜度表示法

T(n)表示算法的執(zhí)行時間，n表示數(shù)據(jù)規(guī)模的大小，f（n）表示每行代碼執(zhí)行的次數(shù)總和。公式中的 O，表示代碼的執(zhí)行時間 T(n) 與 f(n) 表達式成正比。

大 O 時間復(fù)雜度實際上并不具體表示代碼真正的執(zhí)行時間，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢，所以，也叫作漸進時間復(fù)雜度（asymptotic time complexity），簡稱時間復(fù)雜度。

時間復(fù)雜度分析

如何分析一段代碼的時間復(fù)雜度？有三個比較實用的方法

關(guān)注循環(huán)次數(shù)最多的一段代碼

加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度

乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積

幾種常見時間復(fù)雜度

1.、O(1):一般情況下，只要算法中不存在循環(huán)語句、遞歸語句，即使有成千上萬行的代碼，其時間復(fù)雜度也是Ο(1)。

2、O(logn)、O(nlogn)對數(shù)階時間復(fù)雜度非常常見，同時也是最難分析的一種時間復(fù)雜度。我通過一個例子來說明一下。

3、O(m+n)、O(m*n)：代碼的復(fù)雜度由兩個數(shù)據(jù)的規(guī)模來決定

空間復(fù)雜度分析

空間復(fù)雜度全稱就是漸進空間復(fù)雜度（asymptotic space complexity），表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系

我們常見的空間復(fù)雜度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 這樣的對數(shù)階復(fù)雜度平時都用不到。而且，空間復(fù)雜度分析比時間復(fù)雜度分析要簡單很多。所以，對于空間復(fù)雜度，掌握剛我說的這些內(nèi)容已經(jīng)足夠了。

?

?

總結(jié)

以上是生活随笔為你收集整理的03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。