1.時間空間復(fù)雜度定義

1) 時間復(fù)雜度

時間復(fù)雜度表示一個程序運(yùn)行所需要的時間，其具體需要在機(jī)器環(huán)境中才能得到具體的值，但我們一般并不需要得到詳細(xì)的值，只是需要比較快慢的區(qū)別即可，為此，我們需要引入時間頻度（語句頻度）的概念。

時間頻度中，n稱為問題的規(guī)模，當(dāng)n不斷變化時,時間頻度T(n)也會不斷變化。一般情況下，算法中的基本操作重復(fù)次數(shù)的是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。

2)空間復(fù)雜度

一個程序的空間復(fù)雜度是指運(yùn)行完一個程序所需內(nèi)存的大小，其包括兩個部分。

a)固定部分。這部分空間的大小與輸入/輸出的數(shù)據(jù)的個數(shù)多少、數(shù)值無關(guān)。主要包括指令空間（即代碼空間）、數(shù)據(jù)空間（常量、簡單變量）等所占的空間。這部分屬于靜態(tài)空間。

b)可變空間，這部分空間的主要包括動態(tài)分配的空間，以及遞歸棧所需的空間等。這部分的空間大小與算法有關(guān)。

2. 度量時間復(fù)雜度的兩種方法

1)事后統(tǒng)計法

顧名思義，就是指在程序運(yùn)行結(jié)束之后直接查看運(yùn)行時間的方式進(jìn)行時間復(fù)雜度的統(tǒng)計，通常采用利用計算機(jī)的計時器對不同算法編制的程序進(jìn)行運(yùn)行時間的比較，從而確認(rèn)一個算法的效率。

但這種方法有很多缺陷：

a)特別依賴計算機(jī)環(huán)境，同一套算法可能在不同的計算機(jī)上面有著截然不同的效果，老式的計算機(jī)和現(xiàn)代電腦的算力完完全全不是一個級別的處理速度。

b)算法的測試?yán)щy，有時一套算法需要海量的數(shù)據(jù)才能真正比較出效果，而為了設(shè)計這樣的海量數(shù)據(jù)以及正確性，則需要花費(fèi)大量的時間，而對于不同的數(shù)據(jù)，同一算法又有不一樣的效果，故對于數(shù)據(jù)的使用很難去抉擇。

也正是因?yàn)橛羞@樣的缺陷，

2)事先估計法

與事后統(tǒng)計法不一樣，事先統(tǒng)計法采取在計算機(jī)編譯程序前對該算法進(jìn)行預(yù)估的方式估算。我們可以通過利用時間頻度以及函數(shù)的思維進(jìn)行對時間復(fù)雜度的解析。

這里就不得不講函數(shù)符號，它通常用來描述算法的時間復(fù)雜度，其中:

〇表示最壞情況，Ω表示最好情況，θ表示平均情況，我們常用的分析使用O進(jìn)行表示即可。對于一個算法的時間復(fù)雜度而言，n表示其執(zhí)行問題的規(guī)模，O(n)表示執(zhí)行該問題需要的時間量級，如O(n)表示線性級別，O(n²)表示平方級別，其中n主要的判斷方式為算法中循環(huán)結(jié)構(gòu)的執(zhí)行次數(shù)。

以下為一些常用的基本公式：

a)O(a）=O(1)      其中a為常數(shù)

b)O(an)=O(n)     其中a為常數(shù)

c)O(an²⁺+bn+c)=O(n²)      其中a,b,c均為常數(shù)，結(jié)果只與最大項(xiàng)n有關(guān)