原文: 算法復(fù)雜度(一)
date: 2021-01-12 17:42:14
前言
假如計(jì)算機(jī)的處理速度無限快, 存儲(chǔ)空間無限大且廉價(jià), 那似乎就沒有理由來研究算法了.
從目前來看這一點(diǎn)還是不可能的
時(shí)間和空間作為一種資源, 而算法作為一種技術(shù)來研究如何更有效的利用這些資源.
為求解一個(gè)相同的問題而使用不同算法, 其表現(xiàn)出來的效率差異可能非常顯著, 甚至可能超過由硬件和軟件造成的差異.
所以正確理解算法復(fù)雜度分析以及衡量方式至關(guān)重要
目的
寫本文的目的是為了提高自己對(duì)算法復(fù)雜度在理論層面上的認(rèn)知, 著重分享自己的理解與他人分享中比較好的表述. 而且是帶著問題的理解與表述.
不會(huì)過多示例去做算法復(fù)雜度分析, 所以文字占比相較代碼更多.
算法復(fù)雜度
我們分析算法是為了預(yù)測(cè)程序算法所需的資源, 相較內(nèi)存, 網(wǎng)絡(luò)帶寬, 或是其它軟硬件資源來說, 通常我們更加關(guān)心的是算法所耗費(fèi)的時(shí)間資源和空間資源.
那么如何來度量一個(gè)算法程序的時(shí)間和空間呢?
就拿時(shí)間復(fù)雜度來說: 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間從理論上講無法單靠公式精確計(jì)算得出, 所以算法的時(shí)間復(fù)雜度不應(yīng)該單純的理解為算法的執(zhí)行時(shí)間
比較簡單且合理的理解是算法所耗時(shí)間(效率)隨數(shù)據(jù)規(guī)模增長的變化趨勢(shì), 也稱之為漸進(jìn)時(shí)間復(fù)雜度(asymptotic time complexity)
那么類似的, 空間復(fù)雜度表達(dá)的就是算法所耗空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系
重點(diǎn)理解"漸進(jìn)"
BigO Notation
概念&簡單推導(dǎo)
我們經(jīng)?？吹降氖撬惴◤?fù)雜度分析得到一個(gè)帶O的公式結(jié)果, 例如O(n^2), O(logn), O(m+n)...
例如這張圖中列舉了常見排序算法的復(fù)雜度(這里只關(guān)注O即可)
括號(hào)里面的數(shù)學(xué)公式我們都能看懂, 那么這個(gè)大O符號(hào)和變量n是什么意思?
其實(shí)很簡單, 我們只需理解定義 (這里以時(shí)間的復(fù)雜度為例)
一般來說, 算法耗費(fèi)的時(shí)間與輸入的規(guī)模成正比, 如果把算法運(yùn)行的指令數(shù), 或是最簡單的把算法中肉眼可見的每條代碼陳述語句當(dāng)作所消耗的一個(gè)時(shí)間單元的話, 我們可以認(rèn)為算法耗費(fèi)的時(shí)間與運(yùn)行指令數(shù) / 代碼執(zhí)行次數(shù)成正比. 即:
- 運(yùn)行時(shí)間 ∝ 輸入規(guī)模
- 運(yùn)行時(shí)間 ∝ 指令數(shù) / 代碼執(zhí)行的次數(shù)
指令數(shù) / 代碼執(zhí)行次數(shù)是輸入規(guī)模n的某個(gè)函數(shù)f(n), 例如一個(gè)單層循環(huán)中f(n) = n, 雙層嵌套循環(huán)中f(n) = n^2
現(xiàn)在我們只推出了執(zhí)行時(shí)間與指令數(shù)/代碼執(zhí)行次數(shù)的正比關(guān)系, 并不能將T(n)直接與f(n)劃上等號(hào), 并且前面在介紹概念也提到了時(shí)間復(fù)雜度描述的是執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模增長的變化趨勢(shì)
所以我們用O來表示這一含義, 即: T(n) = O(f(n))
所以最最簡單來說大O描述的是算法的運(yùn)行時(shí)間和輸入規(guī)模之間的關(guān)系
其中, 輸入規(guī)模可以是輸入的項(xiàng)數(shù)(例如數(shù)組元素的個(gè)數(shù)n), 或是二進(jìn)制輸入的總位數(shù)(例如求解兩數(shù)相加), 再或其它.
大O有非常嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)定義和證明, 但是在算法分析領(lǐng)域或是應(yīng)對(duì)常見的算法分析, 了解這些已足夠
去除非主導(dǎo)因子
通常我們計(jì)算出的公式可能是多項(xiàng)式, 其中會(huì)包含了低階項(xiàng), 常量, 常量系數(shù)等.
這類項(xiàng)在數(shù)據(jù)規(guī)模不斷增長時(shí)并不能很明顯的左右最終結(jié)果, 可以稱之為非主導(dǎo)因子, 大多時(shí)候應(yīng)該去掉他們
- 去除常量, 系數(shù)常量
- 去除低階項(xiàng)
例如: O(N2 + 2N + 8) 就可以轉(zhuǎn)化為 O(N2), 其中低階項(xiàng)2N和常量8就是非主導(dǎo)因子
再例如:
算法A: 時(shí)間復(fù)雜度為O(n), 其所需執(zhí)行指令數(shù)可能是: 10000n
算法B: 時(shí)間復(fù)雜度為O(n^2), 其所需執(zhí)行指令數(shù)可能是: 10*n^2
前面反復(fù)提到了"漸進(jìn)", 所以大多時(shí)候, 我們不需要耗費(fèi)很多時(shí)間來分析出一個(gè)冗長的函數(shù)來作為復(fù)雜度表達(dá)式, 這也與數(shù)學(xué)中函數(shù)的漸近分析有著很多類似
思考
思考這幾個(gè)問題, 這也是我開始的困惑
1. O 是否一定表示算法最壞情況(上界) ?
從《算法導(dǎo)論》給出的 大O 定義以及數(shù)學(xué)漸近符號(hào)BigO notation定義來講, 它確實(shí)代表漸近上界.
包括很多資料中的描述也是指上界, 因?yàn)樯辖缒苣依ㄋ袛?shù)據(jù)輸入的情況, 某些情況下比較有用.
但在實(shí)際中, 算法的復(fù)雜度除了受輸入數(shù)據(jù)規(guī)模影響外, 還可能受輸入的數(shù)據(jù)形式所影響, 也就是說算法復(fù)雜度分析在有些情況下是用例相關(guān)的
最典型的例子就是輸入數(shù)據(jù)的有序程度對(duì)插入排序和快速排序算法復(fù)雜度的影響
比如我們平常說插入排序是O(n^2)的, 快速排序是O(nlogn)的, 這時(shí)我們描述的就是一般情況, 也就是平均情況 而非最壞.
因?yàn)閷?duì)于排序來說, 完全亂序和本來有序的可能性很低, 所以最壞\最好這兩種特殊情況并不具有普遍意義, 而平均情況更能代表一般情況, 更有意義.
所以大O在業(yè)內(nèi)描述算法時(shí)并不嚴(yán)格指上界
算法中的描述方式勿與數(shù)學(xué)中的漸近符號(hào)描述混淆
例如數(shù)學(xué)中函數(shù)
f(n) = logn的函數(shù)漸近界:O(logn)和O(n)都可以說是它的上界, 但在算法領(lǐng)域一般不這么看, 就用O表示算法執(zhí)行的最低上界PS: 如果你還不了解數(shù)學(xué)中的函數(shù)漸近界, 那就不用管了, 因?yàn)榛煜涣?/p>
2. 為什么不考慮最好的情況 ?
因?yàn)閷?duì)于大多情況的算法來說, 給定特殊的輸入, 即在最優(yōu)情況下都可以達(dá)到O(1), 并不具有太大意義
3. 為什么要去除非主導(dǎo)因子 ?
最顯著的原因是隨著數(shù)據(jù)規(guī)模的增大, 這些非主導(dǎo)因子的增長速度會(huì)遠(yuǎn)小于主導(dǎo)因子.
你可以輸入幾個(gè)函數(shù)在 GeoGebra圖形計(jì)算器 , 用函數(shù)圖形直觀的感受到
我們前面也說過算法復(fù)雜度表示的是一個(gè)算法執(zhí)行效率與數(shù)據(jù)規(guī)模增長的變化趨勢(shì), 所以:
- 低階項(xiàng)再大也會(huì)被忽略, 因?yàn)樗鼘?duì)增長趨勢(shì)的影響相較高階項(xiàng)來說越來越小;
- 常量再大也會(huì)被忽略, 因?yàn)樗鼘?duì)增長趨勢(shì)并沒有任何影響;
還有另外一個(gè)原因, 實(shí)際上有些項(xiàng)很難被精確分析得到, 通常在分析算法復(fù)雜度時(shí), 也只是把算法程序代碼中肉眼可見的陳述語句當(dāng)作所消耗的一個(gè)時(shí)間單元.
這是粗略的, 因?yàn)閷?shí)際上這些項(xiàng)可能因?yàn)榫幊陶Z言和編譯器的不同, 實(shí)際運(yùn)行時(shí)間和步數(shù)不等, 對(duì)應(yīng)其機(jī)器碼的指令數(shù)也可能不同, 甚至相同的指令在不同的CPU下執(zhí)行的操作也可能不同.
Who care? 所以并不值得花大力氣去把它們精確出來, 在數(shù)據(jù)規(guī)模趨于很大的漸進(jìn)分析中, 我們不用關(guān)注西瓜旁的芝麻
實(shí)際上這些低階項(xiàng)和常數(shù)并不能說是完全沒有意義, 有時(shí)可能會(huì)利用其低階項(xiàng)或常數(shù)更小來優(yōu)化算法
例如在快速排序中, 對(duì)于規(guī)模比較小的數(shù)組轉(zhuǎn)而使用插入排序, 通常這種優(yōu)化能獲得10~15%的提升
4. 大O表示法下的低階復(fù)雜度算法一定比高階復(fù)雜度算法快嗎 ?
例如有這樣兩個(gè)復(fù)雜度分析得到的表達(dá)式
- O(n) : e.g.
T = 40000n + 1 - O(n2): e.g.
T = 2n2 + 1
可以大概算出在數(shù)據(jù)輸入規(guī)模 n<200 的范圍內(nèi), 前者的運(yùn)行時(shí)間T都是大于后者的
所以我們不能認(rèn)為對(duì)于任意輸入, O(n)復(fù)雜度的算法都要快于O(n2)的.
這個(gè)結(jié)論還是有實(shí)際意義的, 如果更高階的算法復(fù)雜度有著比較小的常量因子, 假如你在能明確預(yù)知數(shù)據(jù)規(guī)模不大的情況下, 確實(shí)沒必要選擇或者將其優(yōu)化至更低階復(fù)雜度的算法, 因?yàn)檫@種情況下時(shí)間和空間總是夠用的.
再例如在復(fù)雜度為O(nlogn)快速排序中, 對(duì)于規(guī)模比較小的數(shù)組轉(zhuǎn)而使用復(fù)雜度為O(n2)的插入排序, 通常這種優(yōu)化能獲得10~15%的提升
再結(jié)合上面的問題3. 為什么要去除非主導(dǎo)因子 ?, 我們能看出當(dāng)數(shù)據(jù)規(guī)模較小, 或是常量, 系數(shù)常量, 低階項(xiàng)這些非主導(dǎo)因子很大的情況下, 它們是不應(yīng)該被忽略的~
雖然更低階的復(fù)雜度不一定就快, 但依然具有普遍意義和價(jià)值, 因?yàn)闈u進(jìn)分析中的數(shù)據(jù)規(guī)模理解為數(shù)據(jù)規(guī)模無限增加, 也就是說默認(rèn)基于數(shù)據(jù)規(guī)模很大這樣一個(gè)事實(shí), 算法研究的價(jià)值也在于數(shù)據(jù)規(guī)模較大情況下的效率提升
漸進(jìn)的分析方法對(duì)于某個(gè)算法除很小輸入規(guī)模以外的所有情況都是很好的選擇
空間復(fù)雜度
了解了時(shí)間復(fù)雜度, 類比一下, 算法的空間復(fù)雜度描述的就是存儲(chǔ)空間與輸入規(guī)模的增長關(guān)系, 全稱為漸進(jìn)空間復(fù)雜度
相比之下, 空間復(fù)雜度的分析要比時(shí)間復(fù)雜度簡單.
因?yàn)橥ǔＧ闆r下, 空間復(fù)雜度一般都是O(1), O(n), O(n^2)之類的, 對(duì)數(shù)階等一些復(fù)雜的一般不會(huì)出現(xiàn)
直觀數(shù)據(jù)規(guī)模
簡單做一個(gè)不太準(zhǔn)確, 但卻很有實(shí)際用處的例子
- 簡單代碼模擬幾個(gè)常見復(fù)雜度的算法的運(yùn)行時(shí)間
- 時(shí)間假定為1秒
也就是直觀的來看一下: 1秒左右的時(shí)間不同復(fù)雜度的算法大概能夠處理多大規(guī)模的數(shù)據(jù)
-
O(n)
public void oN(long n) { long sum = 0; for (long i = 0; i < n; i++) { sum ++; } } -
O(nlogn)
public void oNLogN(long n) { long sum = 0; for (long i = 0; i < n; i++) { for (long j = 1; j < n; j = j*2) { sum ++; } } } -
O(n2)
public void oNSquared(long n) { long sum = 0; for (long i = 0; i < n; i++) { for (long j = 0; j < n; j++) { sum ++; } } }
我是在一臺(tái)CPU 2.6GHz的工作電腦上測(cè)試的, 測(cè)試結(jié)果如下:
| 時(shí)間復(fù)雜度 | 數(shù)據(jù)規(guī)模 | 量級(jí)(大約) | 運(yùn)行時(shí)間(大約) |
|---|---|---|---|
O(n) |
13億 | 10^8 (億) | 1s |
O(nlogn) |
3000萬 | 10^7 (千萬) | 1s |
O(n2) |
3萬8 | 10^4 (萬) | 1s |
知道其中一個(gè)算法復(fù)雜度1s能夠處理的數(shù)據(jù)規(guī)模量級(jí), 那么其它幾個(gè)復(fù)雜度1s能夠處理的數(shù)據(jù)量級(jí)也能大致估算到.
因?yàn)闇y(cè)試算法的邏輯很簡單, 實(shí)際估算中你可以適當(dāng)把數(shù)據(jù)規(guī)模/量級(jí)減少
1——10倍左右, 以便做出更符合實(shí)際情況的估算
這個(gè)測(cè)試的目的是對(duì)什么復(fù)雜度的算法, 什么規(guī)模的數(shù)據(jù), 運(yùn)行多長時(shí)間有一個(gè)大概了解. 同時(shí)也驗(yàn)證了算法復(fù)雜度中數(shù)據(jù)規(guī)模與執(zhí)行時(shí)間的正比關(guān)系, 以及它們之間大致的倍數(shù)增長關(guān)系
實(shí)際中運(yùn)行環(huán)境和算法邏輯可能復(fù)雜很多, 所以我們只需要了解一個(gè)大概量級(jí)的差異, 以便我們能夠大致估算遇到的算法問題
你只需要知道能夠預(yù)知數(shù)據(jù)規(guī)模的大概量級(jí)前提下, 這個(gè)算法是運(yùn)行幾秒, 還是幾分鐘, 還是卡死?
再或是要你為生產(chǎn)環(huán)境設(shè)計(jì)一個(gè)秒級(jí)處理百萬級(jí)別數(shù)據(jù)規(guī)模的算法, 很明顯這時(shí)你就不要考慮O(n^2), O(n^3)這樣的算法了, 而是應(yīng)該考慮更低階復(fù)雜度的算法
如何分析一個(gè)算法的復(fù)雜度
基本層面分析
我們?cè)诜治鲆粋€(gè)算法復(fù)雜度時(shí), 不需要考慮程序算法最終變?yōu)闄C(jī)器碼后長什么樣子, 具體執(zhí)行了什么指令, 占用了多少個(gè)字節(jié)等.
只需要
- 簡單的把算法中的每個(gè)陳述語句當(dāng)作所消耗的一個(gè)時(shí)間單元
- 簡單的把開辟的變量或數(shù)據(jù)結(jié)構(gòu)當(dāng)作所消耗的一個(gè)空間單元
這里就只介紹一種最簡單最易理解的一種方法: 頻次計(jì)數(shù)法(Frequency Count Method)
示例
Example 1
累加數(shù)組arr中的前n個(gè)元素
sum(int[] arr, int n) {
int sum = 0; // 1
for (int i = 0; i < n; ++i) { // n+1
sum = sum + arr[i]; // n
}
return sum; // 1
}
時(shí)間復(fù)雜度
代碼注釋中標(biāo)注了每行代碼的執(zhí)行次數(shù)
所以: T(n) = 2n+3 ==> 時(shí)間復(fù)雜度為 O(n)
空間復(fù)雜度
算法中所用到的變量和數(shù)據(jù)結(jié)構(gòu)
| 變量/數(shù)據(jù)結(jié)構(gòu) | 所耗空間單元 |
|---|---|
| arr | n |
| n | 1 |
| sum | 1 |
| i | 1 |
所以: S(n) = n + 3 ==> 空間復(fù)雜度為O(n)
這種的分析起來比較簡單, 所以下面來看幾個(gè)復(fù)雜度為√￣和log的
Example 2
{
int p = 0;
for (i = 1; p <= n; i++) {
p = p + i;
}
}
如果不太容易看出, 可以簡單的枚舉一下
| i | p |
|---|---|
| 1 | 0 +１ |
| 2 | 1 + 2 |
| 3 | 1 + 2 + 3 |
| 4 | 1 + 2 + 3 +4 |
| ... | ... |
| k | 1 + 2 + 3 + 4 + ... + k (注意這里是k, 不是n) |
p到底執(zhí)行了多少次, 可以根據(jù)循環(huán)的終止條件p <= n來得到
所以可以假設(shè)最終執(zhí)行了p (p>n)次
∵ p = 1+2+3+...+k = k(k+1)/2 且 p > n
∴ k(k+1)/2 > n
∴ k^2 + k > 2n 去掉兩邊的低階項(xiàng)和常量得到 k^2 > n
∴ k > √n
得到時(shí)間復(fù)雜度為: O(√n)
同樣下面這個(gè)簡單算法的時(shí)間復(fù)雜度也為O(√n)
for (i = 0; i * i < n; i ++) {
stmt;
}
Example 3
for (i = 1; i < n; i = i * 2) {
stmt;
}
| i |
|---|
| 1 |
| 1 * 2 = 2^1 |
| 1 * 2 * 2 = 2^2 |
| 1 * 2 * 2 * 2 = 2^3 |
| ... |
| 1 * 2 * 2 * 2 * ... * 2 = 2^k |
同樣, 要求出k的值, 循環(huán)終止條件假設(shè)i >= n
∴ 2^k >= n
∴ k >= logn
得到算法時(shí)間復(fù)雜度為 O(logn)
類似的來看這個(gè)
for (i = n; i >= 1; i = i/2 ) {
stmt;
}
| i |
|---|
| n |
| n / 2 |
| n / 2^2 |
| n / 2^3 |
| ... |
| n / 2^k |
根據(jù)循環(huán)終止條件假設(shè) i < 1
∵ n / 2^k < 1
∴ 2^k > n
∴ k >= logn
所以得到時(shí)間復(fù)雜度為O(logn)
Example 4
來看一種組合情況
p = 0;
for (i = 1; i < n; i = 2*i) {
p ++; // 1
}
for (j = 1; j < p; j = 2*j) {
stmt; // 2
}
變量比較多時(shí)注意辨別清楚哪個(gè)是輸入規(guī)模n, 哪個(gè)是臨時(shí)變量
這里的2(loop2)不能直接確定循環(huán)次數(shù), 所以需要先看loop1中p的循環(huán)次數(shù)
- loop 1: p = logn次
- loop 2: logp次
所以, 時(shí)間復(fù)雜度為O(loglogn)
類似的看一下這個(gè)
for (i = 0; i < n; i++) { // 1
for (j = 1; j < n; j = j*2) { // 2
stmt; // 3
}
}
分別分析1,2,3處的執(zhí)行次數(shù):
- n
- n * logn
- n * logn
所以, T(n) = 2nlogn + n, 時(shí)間復(fù)雜度為O(nlogn)
補(bǔ)充
1. 對(duì)數(shù)復(fù)雜度公式中的底
我們看到的復(fù)雜度公式中對(duì)數(shù)函數(shù)一般都是以2為底, 例如: ,
是因?yàn)榇驩復(fù)雜度公式計(jì)算中: 以其它常量為底的log公式(e.g. , a為常數(shù)) 經(jīng)過去非主導(dǎo)因子后都可以轉(zhuǎn)化為 以2為底的log公式. 例如:
可認(rèn)為等同于
, 即
因?yàn)?, 而
是一個(gè)常量
其實(shí)就是對(duì)數(shù)的換底公式, 所以: log以任何數(shù)為底n的對(duì)數(shù) 都等于 一個(gè)常數(shù) * log以2為底n的對(duì)數(shù)
對(duì)數(shù)函數(shù)在沒有底數(shù)時(shí)，默認(rèn)底數(shù)為2
e.g.
2. 通過對(duì)數(shù)公式簡化復(fù)雜度公式
遇到一些比較復(fù)雜的公式例如平方, 對(duì)數(shù)等, 在求大O復(fù)雜度公式時(shí), 可以利用一些對(duì)數(shù)公式來簡化求解
補(bǔ)充一些常用的log公式:
一個(gè)面試題
題目: 有一個(gè)字符串?dāng)?shù)組, 將數(shù)組中的每一個(gè)字符串按照字母序排序; 之后再將整個(gè)字符串?dāng)?shù)組按照字典序排序. 分析整個(gè)操作的時(shí)間復(fù)雜度.
易錯(cuò)答案: O(n*nlogn + nlogn) = O(n2logn)
錯(cuò)誤的原因是沒有將字符串的長度考慮進(jìn)去.
這個(gè)算法的時(shí)間復(fù)雜度應(yīng)該從兩個(gè)維度考慮, 并且這兩者之間沒有關(guān)系:
- 字符串?dāng)?shù)組中最長元素的長度s;
- 數(shù)組中字符串元素的個(gè)數(shù)n;
然后分步來考慮(排序這里假設(shè)選擇O(nlogn)的排序算法):
- 對(duì)一個(gè)字符串元素排序:
O(slogs); - 將數(shù)組中的每一個(gè)字符串按照字母序排序:
O(n) * O(slogs)=O(n*slogs); - 整個(gè)字符串?dāng)?shù)組按照字典序排序:
O(s) * O(nlogn)=O(s*nlogn);
注意3中, 除了比較nlogn次以外, 每次字典序比較還需要耗費(fèi)O(s)
字符串比較不像數(shù)字那樣是O(1)的, 需要考慮進(jìn)去
所以最終的時(shí)間復(fù)雜度為: O(n*slogs) + O(s*nlogn) = O(n*slogs + s*nlogn)
意義
要是說我們?yōu)槭裁葱枰治鏊惴ǖ膹?fù)雜度, 或是說分析一個(gè)算法復(fù)雜度的目的, 我們都應(yīng)該知道答案.
在了解算法復(fù)雜度分析之前, 如果讓你來衡量一個(gè)算法在時(shí)間和空間上的執(zhí)行效率, 相信也不是一個(gè)難題.
比如將算法程序直接在計(jì)算機(jī)上跑一下, 再用一些監(jiān)控工具來監(jiān)控時(shí)間和空間占用即可, 并且這樣的結(jié)果也很直觀
但是是否清楚我們?yōu)槭裁匆x擇這種方式呢? 算法復(fù)雜度分析的優(yōu)勢(shì)和意義在哪里? 二者應(yīng)該怎么選擇?
首先, 直接運(yùn)行測(cè)算結(jié)果或者做基準(zhǔn)測(cè)試都是完全正確的, 它也有個(gè)名字叫"事后統(tǒng)計(jì)法"
但是它有著這樣的局限性:
- 受環(huán)境影響較大. 例如系統(tǒng)運(yùn)行環(huán)境, 處理器, 算法的實(shí)現(xiàn)語言等
- 受數(shù)據(jù)規(guī)模影響較大, 數(shù)據(jù)規(guī)模較小可能無法反映出算法的性能, 具體多大的數(shù)據(jù)規(guī)模則需要準(zhǔn)備很多測(cè)試數(shù)據(jù).
例如排序算法, 我們都知道快排的效率要高于插入排序, 但是在小規(guī)模數(shù)據(jù)下, 這個(gè)對(duì)比結(jié)果可能是相反的 - 對(duì)測(cè)試結(jié)果無法有一個(gè)直觀且感性認(rèn)知, 不好窺其內(nèi)因
正因如此, 我們很不方便用實(shí)際運(yùn)行結(jié)果向別人表達(dá)出某個(gè)算法的效率
比如我現(xiàn)在告訴你, 我剛才用Java這樣一種編譯型語言實(shí)現(xiàn)了一個(gè)算法, 用10w測(cè)試數(shù)據(jù)在CPU 2.7GHz Core i5, Windows系統(tǒng)下跑了0.75s, 你會(huì)是什么反應(yīng)? 覺得是快還是慢呢?
所以我們需要復(fù)雜度分析這樣一個(gè)相對(duì)簡單快捷, 與運(yùn)行環(huán)境無關(guān), 且讓我們能在算法設(shè)計(jì)階段就對(duì)效率有一個(gè)直觀認(rèn)知的分析方法
因?yàn)樗惴◤?fù)雜度分析是漸進(jìn)分析, 所以在有了這樣一個(gè)"事前"的理論分析后再根據(jù)自己的環(huán)境和數(shù)據(jù)規(guī)模再進(jìn)行實(shí)際運(yùn)行測(cè)試, 會(huì)得到更加精準(zhǔn)的結(jié)果
所以二者是相輔相成的
