+文本內(nèi)容是對(duì)王爭《數(shù)據(jù)結(jié)構(gòu)與算法之美》課程的筆記得院， 如果有任何侵權(quán)行為， 請(qǐng)聯(lián)系博主刪除
為什么需要復(fù)雜度分析倡蝙？
很多人對(duì)復(fù)雜度分析有疑問, 認(rèn)為直接在機(jī)器上跑一遍, 就可以得出時(shí)間和空間復(fù)雜度. 對(duì)于這種說法, 我們認(rèn)為是正確的, 并且很多書籍將其稱為事后統(tǒng)計(jì). 但是, 這種方法有很大的局限性.
-
測(cè)試結(jié)果依賴于測(cè)試環(huán)境
不同的硬件對(duì)測(cè)試結(jié)果影響較大
-
測(cè)試結(jié)果受數(shù)據(jù)規(guī)模的影響很大
數(shù)據(jù)規(guī)模的大小和有序度, 對(duì)測(cè)試結(jié)果影響較大
所以, 我們需要一個(gè)不用具體的測(cè)試數(shù)據(jù)來測(cè)試, 就可以粗略地估計(jì)算法的執(zhí)行效率的方法.
大
復(fù)雜度表示法
以一段代碼為例來估計(jì)算法的執(zhí)行時(shí)間
int cal(int n) {
int sum = 0;
int i = 1;
for(; i <= n; ++i){
sum = sum + i;
}
return sum;
}
由于是粗略估計(jì), 假設(shè)每行代碼執(zhí)行的時(shí)間都一樣, 為. 第2晃痴、3行代碼分別需要1個(gè)
的執(zhí)行時(shí)間, 第4妓局、5行都運(yùn)行了
遍, 所以需要
的執(zhí)行時(shí)間, 所以這段代碼總的執(zhí)行時(shí)間就是
. 可以看出來, 所有的代碼執(zhí)行時(shí)間
與每行代碼的執(zhí)行次數(shù)成正比.
再看一段代碼
int cal(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;
}
}
}
根據(jù)以上思路, 可以得出.
從中我們可以總結(jié)得到一個(gè)非常重要的規(guī)律, 所有代碼的執(zhí)行時(shí)間與每行代碼的執(zhí)行次數(shù)
成正比
其中表示代碼執(zhí)行的時(shí)間; n表示數(shù)據(jù)規(guī)模的大小;
表示每行代碼執(zhí)行的次數(shù)總和. 公式中的
, 表示代碼的執(zhí)行時(shí)間
與
表達(dá)式成正比.
所以,
, 這就是大
時(shí)間復(fù)雜度表示法. 大
時(shí)間復(fù)雜度實(shí)際表示的是代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長的變化趨勢(shì), 所以, 也叫做漸進(jìn)時(shí)間復(fù)雜度, 簡稱時(shí)間復(fù)雜度.
當(dāng)很大的時(shí)候, 我們只需記錄一個(gè)最大量級(jí)就可以了, 例如
;
.
時(shí)間復(fù)雜度分析
- 只關(guān)注循環(huán)次數(shù)最多的一段代碼
int cal(int n) {
int sum = 0;
int i = 1;
for(; i <= n; ++i){
sum = sum + i;
}
return sum;
}
總的時(shí)間復(fù)雜度為
- 加法法則: 總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜度
int cal(int n){
int sum_1 = 0;
int p = 1;
for(; p < 100; ++p){
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for(; q<n; ++q){
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for(; i<=n; ++i){
for(; j<=n; ++j){
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
總的時(shí)間復(fù)雜度為
- 乘法法則: 嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
int cal(int n){
int ret = 0;
int i = 1;
for(; i<n; ++i){
ret = ret + f(i);
}
}
int f(int n){
int sum = 0;
int i = 1;
for(; i<n; ++i){
sum = sum + i;
}
return sum;
}
總的時(shí)間復(fù)雜度為
幾種常見時(shí)間復(fù)雜度實(shí)例分析
復(fù)雜度量級(jí)(按數(shù)量級(jí)遞增)
- 常量階
- 對(duì)數(shù)階
- 線性階
- 線性對(duì)數(shù)階
- 平方階
、立方階
次方階
- 指數(shù)階
- 階乘階
將上述時(shí)間復(fù)雜度錯(cuò)略的分為兩類：多項(xiàng)式量級(jí)和非多項(xiàng)式量級(jí). 其中, 非多項(xiàng)式量級(jí)只有兩個(gè): 和
.
我們把時(shí)間復(fù)雜度為非多項(xiàng)式量級(jí)的算法問題叫做NP問題(Non-Deterministic Polynomial, 非確定多項(xiàng)式).
當(dāng)數(shù)據(jù)規(guī)模越來越大時(shí), 非多項(xiàng)式量級(jí)算法的執(zhí)行時(shí)間會(huì)急劇增加.
因此, NP問題不是我們討論的重點(diǎn). 接下來, 我們主要來看幾種常見的多項(xiàng)式時(shí)間復(fù)雜度.
-
只是常量級(jí)時(shí)間復(fù)雜度的一種表示方法, 并不是指只執(zhí)行了一行代碼.
int i = 8;
int j = 6;
int sum = i + j;
只要代碼的執(zhí)行時(shí)間不隨的增長而增長, 這樣代碼的時(shí)間復(fù)雜度都記作
. 一般情況下, 只要算法中不存在循環(huán)語句哺眯、遞歸語句, 即使有成千上萬行代碼, 其時(shí)間復(fù)雜度也是
.
-
谷浅、
i = 1;
while(i<=n){
i = i * 2;
}
從代碼中可以看出, 變量的值為:
通過求解, 就可以知道代碼的執(zhí)行次數(shù). 所以其為
.
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Clog_3n" alt="\log_3n" mathimg="1">就等于, 所以
, 其中
是一個(gè)常量. 因此, 在對(duì)數(shù)時(shí)間復(fù)雜度的表示方法里, 忽略對(duì)數(shù)的"底", 統(tǒng)一表示為
.
如果一段代碼的時(shí)間復(fù)雜度是, 循環(huán)
遍, 時(shí)間復(fù)雜度就是
.
-
、
int call(int m, int n){
int sum_1 = 0;
int i = 1;
for(; i<m; ++i){
sum_1 = sum_1 + 1;
}
int sum_2 = 0;
int j = 1;
for(; j<n; ++j){
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
從代碼中可以看出, 和
是表示兩個(gè)數(shù)據(jù)規(guī)模, 我們無法評(píng)判誰的數(shù)量級(jí)大, 所以, 時(shí)間復(fù)雜度就為
.
乘法類似.
空間復(fù)雜度
空間復(fù)雜度全程就是漸進(jìn)空間復(fù)雜度, 表示算法的存儲(chǔ)空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系.
void print(int n){
int i = 0;
int[] a = new int[n];
for(i; i<n; ++i){
a[i] = i*i;
}
for(i=n-1; i>=0; --i){
print out a[i];
}
}
第行代碼中, 我們申請(qǐng)了一個(gè)空間存儲(chǔ)變量
, 但是它是常量階, 跟數(shù)據(jù)規(guī)模
沒有關(guān)系, 所以忽略. 第
行申請(qǐng)了一個(gè)大小為
的
類型數(shù)組, 除此之外, 剩下的代碼都沒有占用更多的空間, 所以整段代碼的空間
.
常見的空間復(fù)雜度就是、
一疯、
.
學(xué)習(xí)關(guān)鍵
多練
