算法復(fù)雜度作用
數(shù)據(jù)結(jié)構(gòu)和算法本身解決的是“快”和“省”的問題，即如何讓代碼運(yùn)行得更快，如何讓代碼更省存儲(chǔ)空間。所以，執(zhí)行效率是算法一個(gè)非常重要的考量指標(biāo)。
多項(xiàng)式階：隨著數(shù)據(jù)規(guī)模的增長(zhǎng)，算法的執(zhí)行時(shí)間和空間占用，按照多項(xiàng)式的比例增長(zhǎng)。包括，
O(1)（常數(shù)階）、O(logn)（對(duì)數(shù)階）、O(n)（線性階）、O(nlogn)（線性對(duì)數(shù)階）、O(n^2 )（平方階）、O(n^3 )（立方階）
- 非多項(xiàng)式階：隨著數(shù)據(jù)規(guī)模的增長(zhǎng)，算法的執(zhí)行時(shí)間和空間占用暴增，這類算法性能極差。包括，O(2^n )（指數(shù)階）、O(n!)（階乘階
- 算法時(shí)間復(fù)雜度由小到大依次為：Ο(1)＜Ο(logn)＜Ο(n)＜Ο( nlog^n )＜Ο( n^2 ) ＜Ο( n^3 ) ＜…＜Ο( 2^n ) ＜Ο(n!)
[圖片上傳失敗...(image-516b81-1554175993123)]
空間復(fù)雜度
先說空間復(fù)雜度，因?yàn)榭臻g復(fù)雜度比較簡(jiǎ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]
}
}
第 2 行代碼中，我們申請(qǐng)了一個(gè)空間存儲(chǔ)變量 i，但是它是常量階的，跟數(shù)據(jù)規(guī)模 n 沒有關(guān)系，所以我們可以忽略。第 3 行申請(qǐng)了一個(gè)大小為 n 的 int 類型數(shù)組，除此之外，剩下的代碼都沒有占用更多的空間，所以整段代碼的空間復(fù)雜度就是 O(n)。
我們常見的空間復(fù)雜度就是 O(1)、O(n)、O(n)，像 O(logn)、O(nlogn) 這樣的對(duì)數(shù)階復(fù)雜度平時(shí)都用不到。而且，空間復(fù)雜度分析比時(shí)間復(fù)雜度分析要簡(jiǎn)單很多
時(shí)間復(fù)雜度
計(jì)算時(shí)間復(fù)雜度的3個(gè)方法
- 只關(guān)注循環(huán)或遞歸最多的一段代碼
- 加法法則：總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜度
- 乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
(1).對(duì)于一些簡(jiǎn)單的輸入輸出語句或賦值語句,近似認(rèn)為需要O(1)時(shí)間
(2).對(duì)于順序結(jié)構(gòu),需要依次執(zhí)行一系列語句所用的時(shí)間可采用大O下"求和法則"
(3).對(duì)于選擇結(jié)構(gòu),如if語句,它的主要時(shí)間耗費(fèi)是在執(zhí)行then字句或else字句所用的時(shí)間,需注意的是檢驗(yàn)條件也需要O(1)時(shí)間
(4).對(duì)于循環(huán)結(jié)構(gòu),循環(huán)語句的運(yùn)行時(shí)間主要體現(xiàn)在多次迭代中執(zhí)行循環(huán)體以及檢驗(yàn)循環(huán)條件的時(shí)間耗費(fèi),一般可用大O下"乘法法則"
(5)只需計(jì)算基本語句執(zhí)行次數(shù)的數(shù)量級(jí)，只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡(jiǎn)化算法分析，并且使注意力集中在最重要的一點(diǎn)上：增長(zhǎng)率。
例1: O(1)
int cal(int n) {
int sum = 0; //1次頻度
int i = 1;//1次頻度
for (; i <= n; ++i) {//n次頻度
sum = sum + i;//n次頻度
}
return sum;
}
時(shí)間復(fù)雜度 T(n) = O(2n+2)=O(n)
例2: O( n )
int a=0; //1次頻度
int b=1; //1次頻度
for (i=1;i<=n;i++){ //n次頻度
s=a+b;//n次頻度
b=a; //n次頻度
a=s; //n次頻度
}
時(shí)間復(fù)雜度 T(n) = O(4+4n)=O(n)
例3: O( n^2 )
int cal(int n) {
int sum = 0;//1次頻度
int i = 1;//1次頻度
int j = 1;//1次頻度
for (; i <= n; ++i) {//n次頻度
j = 1;//n次頻度
for (; j <= n; ++j) {//n*n次頻度
sum = sum + i * j;//n*n次頻度
}
}
}
時(shí)間復(fù)雜度 T(n) = O(3+2n+2n*n)=O( n^2 )
例4: O( log^n )
for(i=0;i<n;){//f(n)次頻度
i*=2;//f(n)次頻度
}
假設(shè)語句2的頻度是f(n),則：2^f(n) <=n; f(n)<=log^n ; 取最大值f(n)=log^n ;T(n)=O(log^n )
例5:
當(dāng)有若干個(gè)循環(huán)語句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的。
int x=1;
for(i=1;i<=n;i++) {
for(j=1;j<=i;j++){
for(k=1;k<=j;k++){
x++;
}
}
}
該程序段中頻度最大的語句是行號(hào)5，內(nèi)循環(huán)的執(zhí)行次數(shù)雖然與問題規(guī)模n沒有直接關(guān)系，但是卻與外層循環(huán)的變量取值有關(guān)，而最外層循環(huán)的次數(shù)直接與n有關(guān)，因此可以從內(nèi)層循環(huán)向外層分析語句(5)的執(zhí)行次數(shù)：
則該程序段的時(shí)間復(fù)雜度為T(n)=O(n3/6+低次項(xiàng))=O(n3)
最好、最壞情況時(shí)間復(fù)雜度
// n 表示數(shù)組 array 的長(zhǎng)度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
因?yàn)?，要查找的變?x 可能出現(xiàn)在數(shù)組的任意位置。如果數(shù)組中第一個(gè)元素正好是要查找的變量 x，那就不需要繼續(xù)遍歷剩下的 n-1 個(gè)數(shù)據(jù)了，那時(shí)間復(fù)雜度就是 O(1)。
但如果數(shù)組中不存在變量 x，那我們就需要把整個(gè)數(shù)組都遍歷一遍，時(shí)間復(fù)雜度就成了 O(n)。所以，不同的情況下，這段代碼的時(shí)間復(fù)雜度是不一樣的。
平均情況時(shí)間復(fù)雜度(加權(quán)平均時(shí)間復(fù)雜度 或 期望時(shí)間復(fù)雜度)
在數(shù)組的 0～n-1 位置中要查找的變量 x 在數(shù)組中的位置，有 n+1 種情況：不在數(shù)組中。我們把每種情況下，查找需要遍歷的元素個(gè)數(shù)累加起來，然后再除以 n+1，就可以得到需要遍歷的元素個(gè)數(shù)的平均值，即：
[圖片上傳失敗...(image-f1905f-1554175993123)]
前面的推導(dǎo)過程中存在的最大問題就是，沒有將各種情況發(fā)生的概率考慮進(jìn)去。如果我們把每種情況發(fā)生的概率也考慮進(jìn)去，那平均時(shí)間復(fù)雜度的計(jì)算過程就變成了這樣：
[圖片上傳失敗...(image-976878-1554175993123)]
引入概率之后，前面那段代碼的加權(quán)平均值為 (3n+1)/4。用大 O 表示法來表示，去掉系數(shù)和常量，這段代碼的加權(quán)平均時(shí)間復(fù)雜度仍然是 O(n)。
均攤時(shí)間復(fù)雜度
// array 表示一個(gè)長(zhǎng)度為 n 的數(shù)組
// 代碼中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
最理想的情況下，數(shù)組中有空閑空間，我們只需要將數(shù)據(jù)插入到數(shù)組下標(biāo)為 count 的位置就可以了，所以最好情況時(shí)間復(fù)雜度為 O(1)。最壞的情況下，數(shù)組中沒有空閑空間了，我們需要先做一次數(shù)組的遍歷求和，然后再將數(shù)據(jù)插入，所以最壞情況時(shí)間復(fù)雜度為 O(n)。
假設(shè)數(shù)組的長(zhǎng)度是 n，根據(jù)數(shù)據(jù)插入的位置的不同，我們可以分為 n 種情況，每種情況的時(shí)間復(fù)雜度是 O(1)。除此之外，還有一種“額外”的情況，就是在數(shù)組沒有空閑空間時(shí)插入一個(gè)數(shù)據(jù)，這個(gè)時(shí)候的時(shí)間復(fù)雜度是 O(n)。而且，這 n+1 種情況發(fā)生的概率一樣，都是 1/(n+1)。所以，根據(jù)加權(quán)平均的計(jì)算方法，我們求得的平均時(shí)間復(fù)雜度就是：平均時(shí)間復(fù)雜度是O(1)
[圖片上傳失敗...(image-2a5a12-1554175993123)]
我們還是繼續(xù)看在數(shù)組中插入數(shù)據(jù)的這個(gè)例子。每一次 O(n) 的插入操作，都會(huì)跟著 n-1 次 O(1) 的插入操作，所以把耗時(shí)多的那次操作均攤到接下來的 n-1 次耗時(shí)少的操作上，均攤下來，這一組連續(xù)的操作的均攤時(shí)間復(fù)雜度就是 O(1)
分析
// 全局變量，大小為 10 的數(shù)組 array，長(zhǎng)度 len，下標(biāo) i。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往數(shù)組中添加一個(gè)元素
void add(int element) {
if (i >= len) { // 數(shù)組空間不夠了
// 重新申請(qǐng)一個(gè) 2 倍大小的數(shù)組空間
int new_array[] = new int[len*2];
// 把原來 array 數(shù)組中的數(shù)據(jù)依次 copy 到 new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array 復(fù)制給 array，array 現(xiàn)在大小就是 2 倍 len 了
array = new_array;
len = 2 * len;
}
// 將 element 放到下標(biāo)為 i 的位置，下標(biāo) i 加一
array[i] = element;
++i;
}
1. 最好情況時(shí)間復(fù)雜度為 O(1)
2. 最壞情況分析：
最壞情況代碼執(zhí)行的次數(shù)跟每次數(shù)組的長(zhǎng)度有關(guān)
第1次調(diào)用insert的執(zhí)行的次數(shù)為 n ,
第2次調(diào)用insert的執(zhí)行的次數(shù)為 2n ,
第3次調(diào)用insert的執(zhí)行的次數(shù)為 2^2 * n
第k次調(diào)用insert的執(zhí)行的次數(shù)為 2^(k-1) * n
最壞時(shí)間復(fù)雜度為 O(n)。
3. 平均情況分析
當(dāng)每次遇到最壞情況時(shí)數(shù)組會(huì)進(jìn)行2倍擴(kuò)容，原數(shù)組被導(dǎo)入新數(shù)組，雖然數(shù)組的長(zhǎng)度變大了，但是插入操作落在的區(qū)間的長(zhǎng)度是一樣的，分別是0~len-1, len~(2len-1),....；
插入的情況仍是len+1種：0~len-1和插滿之后的O(len)；所以每次插入的概率是：p= 1/len+1，
最后求出加權(quán)平均時(shí)間復(fù)雜度為 1*p + 2*p+ ??? + len*p + len * p = O(1) ;
4. 均攤時(shí)間復(fù)雜度 O(1)
而均攤復(fù)雜度由于每次O(len)的出現(xiàn)都跟著len次O(1)，是前后連貫的，因而將O(len)平攤到前l(fā)en次上，得出平攤復(fù)雜度是O(1)
