1. 大 O 表示法

大 O 表示法指出了算法有多快，讓你能夠比較操作數(shù)，它指出了算法運(yùn)行時(shí)間的增速，而并非以秒為單位的速度。大 O 表示法指出了最糟情況下的運(yùn)行時(shí)間。大 O 表示法在討論運(yùn)行時(shí)間時(shí)，log 指的都是 log2。

2. 復(fù)雜度概念

復(fù)雜度是一個(gè)關(guān)于輸入數(shù)據(jù)量 n 的函數(shù)。假設(shè)你的代碼復(fù)雜度是 f(n)，那么就用個(gè)大寫字母 O 和括號，把 f(n) 括起來就可以了，即 O(f(n))。例如，O(n) 表示的是，復(fù)雜度與計(jì)算實(shí)例的個(gè)數(shù) n 線性相關(guān)；O(logn) 表示的是，復(fù)雜度與計(jì)算實(shí)例的個(gè)數(shù) n 對數(shù)相關(guān)。
?
通常，復(fù)雜度的計(jì)算方法遵循以下幾個(gè)原則：

• 復(fù)雜度與具體的常系數(shù)無關(guān)；

例如 O(n) 和 O(2n) 表示的是同樣的復(fù)雜度。我們詳細(xì)分析下，O(2n) 等于 O(n+n)，也等于 O(n) + O(n)。也就是說，一段 O(2n) 復(fù)雜度的代碼只是先后執(zhí)行兩遍 O(n)，其復(fù)雜度是一致的。

• 多項(xiàng)式級的復(fù)雜度相加的時(shí)候，選擇高者作為結(jié)果；

例如 O(n2)+O(n) 和 O(n2) 表示的是同樣的復(fù)雜度。具體分析一下就是，O(n2)+O(n) = O(n2+n)。隨著 n 越來越大，二階多項(xiàng)式的變化率是要比一階多項(xiàng)式更大的。因此，只需要通過更大變化率的二階多項(xiàng)式來表征復(fù)雜度就可以了。

• ?O(1) 也是表示一個(gè)特殊復(fù)雜度，含義為某個(gè)任務(wù)通過有限可數(shù)的資源即可完成。此處有限可數(shù)的具體意義是，與輸入數(shù)據(jù)量 n 無關(guān)。

例如，你的代碼處理 10 條數(shù)據(jù)需要消耗 5 個(gè)單位的時(shí)間資源，3 個(gè)單位的空間資源。處理 1000 條數(shù)據(jù)，還是只需要消耗 5 個(gè)單位的時(shí)間資源，3 個(gè)單位的空間資源。那么就能發(fā)現(xiàn)資源消耗與輸入數(shù)據(jù)量無關(guān)，就是 O(1) 的復(fù)雜度。
?

3. 常見復(fù)雜度

常見的復(fù)雜度結(jié)論：

• 一個(gè)順序結(jié)構(gòu)的代碼，時(shí)間復(fù)雜度是 O(1)；
• 二分查找，或者更通用地說是采用分而治之的二分策略，時(shí)間復(fù)雜度都是 O(logn)；
• 一個(gè)簡單的 for 循環(huán)，時(shí)間復(fù)雜度是 O(n)；
• 兩個(gè)順序執(zhí)行的 for 循環(huán)，時(shí)間復(fù)雜度是 O(n)+O(n)=O(2n)，其實(shí)也是 O(n)；
• 兩個(gè)嵌套的 for 循環(huán)，時(shí)間復(fù)雜度是 O(n2)；

?

下面按從快到慢的順序列出了經(jīng)常會遇到的 5 種時(shí)間復(fù)雜度：

• O(log n)，也叫對數(shù)時(shí)間，這樣的算法包括二分查找；
• O(n)，也叫線性時(shí)間，這樣的算法包括簡單查找；
• O(n*logn)，這樣的算法包括快速排序 —— 一種速度較快的排序算法；
• O(n2)，這樣的算法包括選擇排序 —— 一種速度較慢的排序算法；
• O(n!)，這樣的算法包括旅行商問題的解決方案 —— 一種非常慢的算法；

3.1 O(1)

比如操作一步到位這是常數(shù)級別的時(shí)間復(fù)雜，即為 O(1)。

a = 100 / 2 + 101 * 10 + 5

3.2 O(logn)

如下操作，每次 n 會被除以 3，遍歷次數(shù)等于以 3 為底 logn 次。在大 O 標(biāo)記體系中，以 3 為底和以 5 為底沒有區(qū)別，所以統(tǒng)一標(biāo)記為 O(logn)。

def f(n):while n > 0:print(n)n /= 3

3.3 o(n)

線型復(fù)雜度也是很理想的情況，如下面的操作，每次遍歷，n 減去 3，這樣總共遍歷 (n-1)/3 + 1 次后算法終止，根據(jù)大 O 標(biāo)記法，算法的時(shí)間復(fù)雜為 O(n)。

def f(n):while n > 0:print(n)n -= 3

3.4 O(nlogn)

如下面所示的兩層循環(huán)，復(fù)雜度便是 nlogn。外層循環(huán)的運(yùn)行次數(shù)為 n，里層循環(huán)的運(yùn)行次數(shù)為 logn 次，所以一共需要 nlogn 次。

def f(n):for i in range(n):n /= 2for j in range(1,n):print(i*j)

3.5 O(n^2)

O(n^2) 是多項(xiàng)式時(shí)間復(fù)雜度的代表，此類算法的時(shí)間復(fù)雜度已經(jīng)難以劃分到高效算法集合中，它只能是問題的有效解，而不是高效解。如下兩層for 循環(huán)，時(shí)間復(fù)雜度就是 O(n^2)。

def f(n):for i in range(n):for j in range(n):print(i*j)

3.6 O(2^n)

時(shí)間復(fù)雜度為 O(2^n) 的算法是指數(shù)級增長的，此類復(fù)雜度下求解的問題往往都是難題，因?yàn)殡S著問題規(guī)模 n的增長，指數(shù)級的增長速度是驚人的。

例如經(jīng)典的旅行商問題，商人要去 n個(gè)地方拜訪，如何規(guī)劃拜訪順序才能使得旅行距離最短。如果僅拜訪肉眼可見的兩三個(gè)地方時(shí)，我們還能窮舉所有拜訪的組合，進(jìn)而找到最短路徑。

但是當(dāng)問題規(guī)模 n 變大時(shí)，目前所有的計(jì)算機(jī)資源總和都難以在有限的時(shí)間里計(jì)算出最優(yōu)的最短路徑，這類問題的時(shí)間復(fù)雜度都為指數(shù)級，屬于 NP 難問題。

總結(jié)

以上是生活随笔為你收集整理的数据结构（01）— 算法复杂度概念及常见的复杂度计算的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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