一、前言
在進一步學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法前,我們應(yīng)該先掌握算法分析的一般方法。算法分析主要包括對算法的時空復(fù)雜度進行分析,但有些時候我們更關(guān)心算法的實際運行性能如何,此外,算法可視化是一項幫助我們理解算法實際執(zhí)行過程的實用技能,在分析一些比較抽象的算法時,這項技能尤為實用。
在本文中,我們首先會介紹如何通過設(shè)計實驗來量化算法的實際運行性能,然后會介紹算法的時間復(fù)雜度的分析方法,我們還會介紹能夠非常便捷的預(yù)測算法性能的倍率實驗。當(dāng)然,在文章的末尾,我們會一起來做幾道一線互聯(lián)網(wǎng)的相關(guān)面試/筆試題來鞏固所學(xué),達到學(xué)以致用。
二、算法分析的一般方法
1、量化算法的實際運行性能
在介紹算法的時空復(fù)雜度分析方法前,我們先來介紹以下如何來量化算法的實際運行性能,這里我們選取的衡量算法性能的量化指標(biāo)是它的實際運行時間。通常這個運行時間與算法要解決的問題規(guī)模相關(guān),比如排序100萬個數(shù)的時間通常要比排序10萬個數(shù)的時間要長。所以我們在觀察算法的運行時間時,還要同時考慮它所解決問題的規(guī)模,觀察隨著問題規(guī)模的增長,算法的實際運行時間時怎樣增長的。這里我們采用算法(第4版) (豆瓣)一書中的例子,代碼如下:
public class ThreeSum {
public static int count(int[] a) {
int N = a.length;
int cnt = 0;
for (int i = 0; i < N; i++) { ?
? ? ? ? ? ?for (int j = i + 1; j < N; j++) { ?
? ? ? ? ? ? ? ?for (int k = j + 1; k < N; k++) { ?
? ? ? ? ? ? ? ? ? ?if (a[i] + a[j] + a[k] == 0) {
cnt++;
}
}
}
}
return cnt;
}
public static void main(String[] args) {
int[] a = StdIn.readAllInts();
StdOut.println(count(a));
}
}
以上代碼用到的StdIn和StdOut這兩個類都在這里:
https://github.com/absfree/Algo。我們可以看到,以上代碼的功能是統(tǒng)計標(biāo)準一個int[]數(shù)組中的所有和為0的三整數(shù)元組的數(shù)量。采用的算法十分直接,就是從頭開始遍歷數(shù)組,每次取三個數(shù),若和為0,則計數(shù)加一,最后返回的計數(shù)值即為和為0的三元組的數(shù)量。這里我們采取含有整數(shù)數(shù)量分別為1000、2000、4000的3個文件(這些文件可以在上面的項目地址中找到),來對以上算法進行測試,觀察它的運行時間隨著問題規(guī)模的增長是怎樣變化的。
測量一個過程的運行時間的一個直接的方法就是,在這個過程運行前后各獲取一次當(dāng)前時間,兩者的差值即為這個過程的運行時間。當(dāng)我們的過程本身需要的執(zhí)行時間很短時間,這個測量方法可能會存在一些誤差,但是我們可以通過執(zhí)行多次這個過程再取平均數(shù)來減小以至可以忽略這個誤差。下面我們來實際測量一下以上算法的運行時間,相關(guān)代碼如下:
public static void main(String[] args) {
int[] a = In.readInts(args[0]);
long startTime = System.currentTimeMillis();
int count = count(a);
long endTime = System.currentTimeMillis();
double time = (endTime - startTime) / 1000.0;
StdOut.println("The result is: " + count + ", and takes " + time + " seconds.");
}
我們分別以1000、2000、4000個整數(shù)作為輸入,得到的運行結(jié)果如下
The result is: 70, and takes 1.017 seconds. //1000個整數(shù) The result is: 528, and takes 7.894 seconds. //2000個整數(shù) The result is: 4039, and takes 64.348 seconds. //4000個整數(shù)
我們從以上結(jié)果大概可你看到,當(dāng)問題的規(guī)模變?yōu)樵瓉淼?倍時,實際運行時間大約變?yōu)樵瓉淼?倍。根據(jù)這個現(xiàn)象我們可以做出一個猜想:程序的運行時間關(guān)于問題規(guī)模N的函數(shù)關(guān)系式為T(N) = k*(n^3).
在這個關(guān)系式中,當(dāng)n變?yōu)樵瓉淼?倍時,T(N)會變?yōu)樵瓉淼?倍。那么ThreeSum算法的運行時間與問題規(guī)模是否滿足以上的函數(shù)關(guān)系呢?在介紹算法時間復(fù)雜度的相關(guān)內(nèi)容后,我們會回過頭來再看這個問題。
2、算法的時間復(fù)雜度分析
(1)基本概念
關(guān)于算法的時間復(fù)雜度,這里我們先簡單介紹下相關(guān)的三種符號記法:
-
第一種叫Big O notation,它給出了運行時間的”漸進上界“,也就是算法在最壞情況下運行時間的上限。它的定義如下:對于f(n)和g(n),若存在常數(shù)c和N0,使得對于所有n > N0,都有 |f(n)| < c * g(n),則稱f(n)為O(g(n)。
-
第三種叫做BigΩ notation,它給出了運行時間的“漸進下界”,也就是算法在最壞情況下運行時間的下限。它的定義如下:對于f(n)和g(n),若存在常數(shù)c和N0,使得對于所有n > N0,都有|f(n)| > c * g(n),則稱f(n)為Ω(g(n))。
-
第三種叫BigΘ notation,它確定了運行時間的”漸進確界“。定義如下:對于f(n)和g(n),若存在常數(shù)c和N0,對于所有n> N0,都有|f(n)| = c * g(n),則稱f(n)為Θ為Θ(g(n))。
我們在平常的算法分析中最常用到的是Big O notation。下面我們將介紹分析算法的時間復(fù)雜度的具體方法,若對Big O notation的概念還不是很了解,推薦大家看這篇文章:http://blog.jobbole.com/55184/。
(2)時間復(fù)雜度的分析方法
這部分我們將以上面的ThreeSum程序為例,來介紹一下算法時間復(fù)雜度的分析方法。為了方便閱讀,這里再貼一下上面的程序:
public static int count(int[] a) {
int N = a.length;
int cnt = 0;
for (int i = 0; i < N; i++) { ?
? ? ? ? ? ?for (int j = i + 1; j < N; j++) { ?
? ? ? ? ? ? ? ?for (int k = j + 1; k < N; k++) { ?
? ? ? ? ? ? ? ? ? ?if (a[i] + a[j] + a[k] == 0) {
cnt++;
}
}
}
}
return cnt;
}
在介紹時間復(fù)雜度分析方法前,我們首先來明確下算法的運行時間究竟取決于什么。直觀地想,一個算法的運行時間也就是執(zhí)行所有程序語句的耗時總和。然而在實際的分析中,我們并不需要考慮所有程序語句的運行時間,我們應(yīng)該做的是集中注意力于最耗時的部分,也就是執(zhí)行頻率最高而且最耗時的操作。也就是說,在對一個程序的時間復(fù)雜度進行分析前,我們要先確定這個程序中哪些語句的執(zhí)行占用的它的大部分執(zhí)行時間,而那些盡管耗時大但只執(zhí)行常數(shù)次(和問題規(guī)模無關(guān))的操作我們可以忽略。我們選出一個最耗時的操作,通過計算這些操作的執(zhí)行次數(shù)來估計算法的時間復(fù)雜度,下面我們來具體介紹這一過程。
首先我們看到以上代碼的第1行和第2行的語句只會執(zhí)行一次,因此我們可以忽略它們。然后我們看到第4行到第12行是一個三層循環(huán),最內(nèi)存的循環(huán)體包含了一個if語句。也就是說,這個if語句是以上代碼中耗時最多的語句,我們接下來只需要計算if語句的執(zhí)行次數(shù)即可估計出這個算法的時間復(fù)雜度。以上算法中,我們的問題規(guī)模為N(輸入數(shù)組包含的元素數(shù)目),我們也可以看到,if語句的執(zhí)行次數(shù)與N是相關(guān)的。我們不難得出,if語句會執(zhí)行N * (N - 1) * (N - 2) / 6次,因此這個算法的時間復(fù)雜度為O(n^3)。這也印證了我們之前猜想的運行時間與問題規(guī)模的函數(shù)關(guān)系(T(n) = k * n ^ 3)。由此我們也可以知道,算法的時間復(fù)雜度刻畫的是隨著問題規(guī)模的增長,算法的運行時間的增長速度是怎樣的。在平常的使用中,Big O notation通常都不是嚴格表示最壞情況下算法的運行時間上限,而是用來表示通常情況下算法的漸進性能的上限,在使用Big O notation描述算法最壞情況下運行時間的上限時,我們通常加上限定詞“最壞情況“。
通過以上分析,我們知道分析算法的時間復(fù)雜度只需要兩步(比把大象放進冰箱還少一步:) ):
-
尋找執(zhí)行次數(shù)多的語句作為決定運行時間的[關(guān)鍵操作];
-
分析關(guān)鍵操作的執(zhí)行次數(shù)。
在以上的例子中我們可以看到,不論我們輸入的整型數(shù)組是怎樣的,if語句的執(zhí)行次數(shù)是不變的,也就是說上面算法的運行時間與輸入無關(guān)。而有些算法的實際運行時間高度依賴于我們給定的輸入,關(guān)于這一問題下面我們進行介紹。
3、算法的期望運行時間
算法的期望運行時間我們可以理解為,在通常情況下,算法的運行時間是多少。在很多時候,我們更關(guān)心算法的期望運行時間而不是算法在最壞情況下運行時間的上限,因為最壞情況和最好情況發(fā)生的概率是比較低的,我們更常遇到的是一般情況。比如說盡管快速排序算法與歸并排序算法的時間復(fù)雜度都為O(nlogn),但是在相同的問題規(guī)模下,快速排序往往要比歸并排序快,因此快速排序算法的期望運行時間要比歸并排序的期望時間小。然而在最壞情況下,快速排序的時間復(fù)雜度會變?yōu)镺(n^2),快速排序算法就是一個運行時間依賴于輸入的算法,對于這個問題,我們可以通過打亂輸入的待排序數(shù)組的順序來避免發(fā)生最壞情況。
4、倍率實驗
下面我們來介紹一下算法(第4版) (豆瓣)一書中的“倍率實驗”。這個方法能夠簡單有效地預(yù)測程序的性能并判斷他們的運行時間大致的增長數(shù)量級。在正式介紹倍率實驗前,我們先來簡單介紹下“增長數(shù)量級“這一概念(同樣引用自《算法》一書):
我們用~f(N)表示所有隨著N的增大除以f(N)的結(jié)果趨于1的函數(shù)。用g(N)~f(N)表示g(N) / f(N)隨著N的增大趨近于1。通常我們用到的近似方式都是g(N) ~ a * f(N)。我們將f(N)稱為g(N)的增長數(shù)量級。
我們還是拿ThreeSum程序來舉例,假設(shè)g(N)表示在輸入數(shù)組尺寸為N時執(zhí)行if語句的次數(shù)。根據(jù)以上的定義,我們就可以得到g(N) ~ N ^ 3(當(dāng)N趨向于正無窮時,g(N) / N^3 趨近于1)。所以g(N)的增長數(shù)量級為N^3,即ThreeSum算法的運行時間的增長數(shù)量級為N^3。
現(xiàn)在,我們來正式介紹倍率實驗(以下內(nèi)容主要引用自上面提到的《算法》一書,同時結(jié)合了一些個人理解)。首先我們來一個熱身的小程序:
public class DoublingTest {
public static double timeTrial(int N) {
int MAX = 1000000;
int[] a = new int[N];
for (int i = 0; i < N; i++) { ?
? ? ? ? ? ?a[i] = StdRandom.uniform(-MAX, MAX); ?
? ? ? ?} ?
? ? ? ?long startTime = System.currentTimeMillis();
int count = ThreeSum.count(a);
long endTime = System.currentTimeMillis();
double time = (endTime - startTime) / 1000.0;
return time;
}
public static void main(String[] args) {
for (int N = 250; true; N += N) {
double time = timeTrial(N);
StdOut.printf("%7d %5.1f\n", N, time);
}
}
}
以上代碼會以250為起點,每次講ThreeSum的問題規(guī)模翻一倍,并在每次運行ThreeSum后輸出本次問題規(guī)模和對應(yīng)的運行時間。運行以上程序得到的輸出如下所示:
250 0.0 500 0.1 1000 0.6 2000 4.3 4000 30.6
上面的輸出之所以和理論值有所出入是因為實際運行環(huán)境是復(fù)雜多變的,因而會產(chǎn)生許多偏差,盡可能減小這種偏差的方式就是多次運行以上程序并取平均值。有了上面這個熱身的小程序做鋪墊,接下來我們就可以正式介紹這個“可以簡單有效地預(yù)測任意程序執(zhí)行性能并判斷其運行時間的大致增長數(shù)量級”的方法了,實際上它的工作基于以上的DoublingTest程序,大致過程如下:
-
開發(fā)一個[輸入生成器]來產(chǎn)生實際情況下的各種可能的輸入。
-
反復(fù)運行下面的DoublingRatio程序,直至time/prev的值趨近于極限2^b,則該算法的增長數(shù)量級約為N^b(b為常數(shù))。
DoublingRatio程序如下:
運行倍率程序,我們可以得到如下輸出:
0.0 2.0 0.1 5.5 0.5 5.4 3.7 7.0 27.4 7.4 218.0 8.0
我們可以看到,time/prev確實收斂到了8(2^3)。那么,為什么通過使輸入不斷翻倍而反復(fù)運行程序,運行時間的比例會趨于一個常數(shù)呢?答案是下面的[倍率定理]:
若T(N) ~ a * N^b * lgN,那么T(2N) / T(N) ~2^b。
以上定理的證明很簡單,只需要計算T(2N) / T(N)在N趨向于正無窮時的極限即可。其中,“a * N^b * lgN”基本上涵蓋了常見算法的增長量級(a、b為常數(shù))。值得我們注意的是,當(dāng)一個算法的增長量級為NlogN時,對它進行倍率測試,我們會得到它的運行時間的增長數(shù)量級約為N。實際上,這并不矛盾,因為我們并不能根據(jù)倍率實驗的結(jié)果推測出算法符合某個特定的數(shù)學(xué)模型,我們只能夠大致預(yù)測相應(yīng)算法的性能(當(dāng)N在16000到32000之間時,14N與NlgN十分接近)。
5、均攤分析
考慮下我們之前在 深入理解數(shù)據(jù)結(jié)構(gòu)之鏈表 中提到的ResizingArrayStack,也就是底層用數(shù)組實現(xiàn)的支持動態(tài)調(diào)整大小的棧。每次添加一個元素到棧中后,我們都會判斷當(dāng)前元素是否填滿的數(shù)組,若是填滿了,則創(chuàng)建一個尺寸為原來兩倍的新數(shù)組,并把所有元素從原數(shù)組復(fù)制到新數(shù)組中。我們知道,在數(shù)組未填滿的情況下,push操作的復(fù)雜度為O(1),而當(dāng)一個push操作使得數(shù)組被填滿,創(chuàng)建新數(shù)組及復(fù)制這一工作會使得push操作的復(fù)雜度驟然上升到O(n)。
對于上面那種情況,我們顯然不能說push的復(fù)雜度是O(n),我們通常認為push的“平均復(fù)雜度”為O(1),因為畢竟每n個push操作才會觸發(fā)一次“復(fù)制元素到新數(shù)組”,因而這n個push把這一代價一均攤,對于這一系列push中的每個來說,它們的均攤代價就是O(1)。這種記錄所有操作的總成本并除以操作總數(shù)來講成本均攤的方法叫做均攤分析(也叫攤還分析)。
三、小試牛刀之實戰(zhàn)名企面試題
前面我們介紹了算法分析的一些姿勢,那么現(xiàn)在我們就來學(xué)以致用,一起來解決幾道一線互聯(lián)網(wǎng)企業(yè)有關(guān)于算法分析的面試/筆試題。
【騰訊】下面算法的時間復(fù)雜度是____
int foo(int n) {
if (n <= 1) {
return 1;
}
return n * foo(n - 1);
}
看到這道題要我們分析算法時間復(fù)雜度后,我們要做的第一步便是確定關(guān)鍵操作,這里的關(guān)鍵操作顯然是if語句,那么我們只需要判斷if語句執(zhí)行的次數(shù)即可。首先我們看到這是一個遞歸過程:foo會不斷的調(diào)用自身,直到foo的實參小于等于1,foo就會返回1,之后便不會再執(zhí)行if語句了。由此我們可以知道,if語句調(diào)用的次數(shù)為n次,所以時間復(fù)雜度為O(n)。
【京東】以下函數(shù)的時間復(fù)雜度為____
void recursive(int n, int m, int o) {
if (n <= 0) {
printf("%d, %d\n", m, o);
} else {
recursive(n - 1, m + 1, o);
recursive(n - 1, m, o + 1);
}
}
這道題明顯要比上道題難一些,那么讓我們來按部就班的解決它。首先,它的關(guān)鍵操作時if語句,因此我們只需判斷出if語句的執(zhí)行次數(shù)即可。以上函數(shù)會在n > 0的時候不斷遞歸調(diào)用自身,我們要做的是判斷在到達遞歸的base case(即n <= 0)前,共執(zhí)行了多少次if語句。我們假設(shè)if語句的執(zhí)行次數(shù)為T(n, m, o),那么我們可以進一步得到:T(n, m, o) = T(n-1, m+1, o) + T(n-1, m, o+1) (當(dāng)n > 0時)。我們可以看到base case與參數(shù)m, o無關(guān),因此我們可以把以上表達式進一步簡化為T(n) = 2T(n-1),由此我們可得T(n) = 2T(n-1) = (2^2) * T(n-2)......所以我們可以得到以上算法的時間復(fù)雜度為O(2^n)。
【京東】如下程序的時間復(fù)雜度為____(其中m > 1,e > 0)
x = m;
y = 1;
while (x - y > e) {
x = (x + y) / 2;
y = m / x;
}
print(x);
以上算法的關(guān)鍵操作即while語句中的兩條賦值語句,我們只需要計算這兩條語句的執(zhí)行次數(shù)即可。我們可以看到,當(dāng)x - y > e時,while語句體內(nèi)的語句就會執(zhí)行,x = (x + y) / 2使得x不斷變?。ó?dāng)y<
【搜狗】假設(shè)某算法的計算時間可用遞推關(guān)系式T(n) = 2T(n/2) + n,T(1) = 1表示,則該算法的時間復(fù)雜度為____
根據(jù)題目給的遞推關(guān)系式,我們可以進一步得到:T(n) = 2(2T(n/4) + n/2) + n = ... 將遞推式進一步展開,我們可以得到該算法的時間復(fù)雜度為O(nlogn),這里就不貼上詳細過程了。
-
算法
+關(guān)注
關(guān)注
23文章
4552瀏覽量
92019 -
數(shù)據(jù)結(jié)構(gòu)
+關(guān)注
關(guān)注
3文章
568瀏覽量
40030 -
量化算法
+關(guān)注
關(guān)注
0文章
4瀏覽量
6473
原文標(biāo)題:算法分析的正確姿勢
文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論