複雜度分析筆記

複雜度分析筆記（時間複雜度、空間複雜度）

一、什麼是複雜度分析？

資料結構和算法解決的是如何讓計算機更快時間、更省空間的問題。是以需從執行時間和占用空間兩個次元來評估資料結構和算法的性能。分别用時間複雜度和空間複雜度兩個概念來描述性能問題，二者統稱為複雜度。 複雜度描述的是算法執行時間（或占用空間）與資料規模的增長關系，是以又稱漸進時間複雜度、漸進空間複雜度

二、為什麼要進行複雜度分析？

• 和性能測試相比，複雜度分析有不依賴執行環境、成本低、效率高、易操作、指導性強的特點。
• 我們可以不用具體的測試資料來測試，就可以粗略地估計算法的執行效率。
• 掌握複雜度分析，将能編寫出性能更優的代碼，有利于降低系統開發和維護成本。

大 O 複雜度表示法

我們通常用大O複雜度表示法來表示算法的時間複雜度和空間複雜度

下面将用大 O 複雜度表示法來表示這兩段代碼

• 例1

int fun(int n) { 
	int sum = 0; 
	int i = 1; 
	for (; i <= n; ++i) { 
		sum = sum + i; 
		} 
	return sum; 
}
           

對于上面一段代碼我們可以假設每行代碼執行的時間都一樣，為unit_time。第 2、3 行代碼分别需要 1 個 unit_time 的執行時間，第 4、5 行都運作了 n 遍，是以需要 2n*unit_time 的執行時間，是以這段代碼總的執行時間(2n+2)*unit_time。可以看出來，所有代碼的執行時間 T(n) 與每行代碼的執行次數成正比。

• 例2

int fun(int n) { 
 	int sum = 0; 
	int i = 1; 
	int j = 1; 
 	for (; i <= n; ++i) { 
 		j = 1; 
 		for (; j <= n; ++j) { 
 			sum = sum + i * j; 
	 	} 
	 } 
 }
           

同理上段代碼總的執行時間 T(n) = (2n2+2n+3)*unit_time

盡管我們不知道 unit_time 的具體值，但是通過這兩段代碼執行時間的推導過程，我們可以得到一個非常重要的規律，那就是，所有代碼的執行時間 T(n) 與每行代碼的執行次數 n 成正比。

這個規律總結成一個公式就是T(n)=O(f(n))。其中T(n)表示代碼執行的時間；n 表示資料規模的大小；f(n) 表示每行代碼執行的次數總和。公式中的 O，表示代碼的執行時間 T(n) 與 f(n) 表達式成正比。

故上述兩個例子的時間複雜度分别表示為T(n) = O(2n+2)，T(n) = O(2n2+2n+3)。公式中的低階、常量、系數三部分并不左右增長趨勢，是以都可以忽略。我們隻需要記錄一個最大量級就可以了，如果用大 O 表示法表示剛講的那兩段代碼的時間複雜度，就可以記為：T(n) = O(n)； T(n) = O(n2)。

如何分析時間複雜度?

1. 隻關注循環執行次數最多的一段代碼

就例1而言，其中第 2、3 行代碼都是常量級的執行時間，與 n 的大小無關，是以對于複雜度并沒有影響。循環執行次數最多的是第 4、5 行代碼，是以這塊代碼要重點分析。前面我們也講過，這兩行代碼被執行了 n 次，是以總的時間複雜度就是 O(n)。

int fun(int n) { 
	int sum = 0; 
	for (int i=1; i <= n; ++i) { 
		sum = sum + i; 
	} 
	return sum; 
}
           

2. 加法法則：總複雜度等于量級最大的那段代碼的複雜度`

• 例3

int fun(int n) { 
	int sum_1 = 0; 
	for (int p=1; p < 100; ++p) { 
			sum_1 = sum_1 + p; 
		} 
	int sum_2 = 0; 
	for (int q=1; q < n; ++q) { 
			sum_2 = sum_2 + q; 
		} 
	int sum_3 = 0; 
	for (int i=1; i <= n; ++i) {  
		for (int j=1; j <= n; ++j) { 
			sum_3 = sum_3 + i * j; 
		} 
	} 
	return sum_1 + sum_2 + sum_3;
}
           

首先看第一段代碼，這段代碼循環執行了 100 次，是以是一個常量的執行時間，跟 n 的規模無關。

因為時間複雜度表示的是一個算法執行效率與資料規模增長的變化趨勢，是以不管常量的執行時間多大，我們都可以忽略掉。因為它本身對增長趨勢并沒有影響。

第二段代碼和第三段代碼的時間複雜度是是 O(n) 和 O(n2)。綜合這三段代碼的時間複雜度，我們取其中最大的量級。是以，整段代碼的時間複雜度就為 O(n2)。也就是說：總的時間複雜度就等于量級最大的那段代碼的時間複雜度。

那我們将這個規律抽象成公式就是：

如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那麼 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).

3. 乘法法則：嵌套代碼的複雜度等于嵌套内外代碼複雜度的乘積

可以把乘法法則看成是嵌套循環

類比加法法則，可以得出：如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那麼 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)).

多項式時間複雜度

O(1) 隻是常量級時間複雜度的一種表示方法，并不是指隻執行了一行代碼。比如：

int i=1;
int j=1;
           

1. O(1)

一般情況下，隻要算法中不存在循環語句、遞歸語句，即使有成千上萬行的代碼，其時間複雜度也是Ο(1)。

2. O(logn)、O(nlogn)

int i=1;
while (i <= n) {
	i = i * 2; 
}
           

從代碼中可以看出，變量 i 的值從 1 開始取，每循環一次就乘以 2。當大于 n 時，循環結束。這實際上就是等比數列2x=n,x=log2n。x就是代碼執行的次數。

由于對數之間是可以互相轉換的，log3n 就等于 log32 * log2n，即O(Cf(n)) = O(f(n))

是以，在對數階時間複雜度的表示方法裡，我們忽略對數的“底”，統一表示為 O(logn)。

3. O(m+n)、O(m*n)

這一種跟前面都不一樣的時間複雜度，代碼的複雜度由兩個資料的規模來決定。

int fun(int m, int n) { 
	int sum_1 = 0;  
	for (int i=1; i < m; ++i) { 
		sum_1 = sum_1 + i; 
	} 
	int sum_2 = 0;  
	for (int j=1; j < n; ++j) { 
		sum_2 = sum_2 + j; 
	} 
	return sum_1 + sum_2;
}
           

m 和 n 是表示兩個資料規模。我們無法事先評估 m 和 n 誰的量級大，是以我們在表示複雜度的時候，就不能簡單地利用加法法則，省略掉其中一個。是以，上面代碼的時間複雜度就是 O(m+n)。

故加法規則改為：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法則繼續有效：T1(m)*T2(n) = O(f(m) * f(n))。

空間複雜度分析

1、定義：算法存儲空間與資料規模增長的關系，主要看聲明的空間存儲變量所需要的控件存儲量

2、O(1)、O(n)、O(n2)，可參考基本資料類型、一維數組、二維數組

小結

1）單段代碼看高頻：比如循環。

2）多段代碼取最大：比如一段代碼中有單循環和多重循環，那麼取多重循環的複雜度。

3）嵌套代碼求乘積：比如遞歸、多重循環等

4）多個規模求加法：比如方法有兩個參數控制兩個循環的次數，那麼這時就取二者複雜度相加。