本文首發(fā)于 LOGI'S BLOG，由作者轉(zhuǎn)載鹰溜。
大 O 表示法
大 O 表示法并不具體表示代碼的實(shí)際執(zhí)行時(shí)間和實(shí)際占用空間罐呼，而代表代碼執(zhí)行時(shí)間和占用空間隨數(shù)據(jù)規(guī)模增加的增長(zhǎng)趨勢(shì)捣染，所以用大 O 表示法定義的時(shí)空復(fù)雜度分別叫做 漸進(jìn)時(shí)間復(fù)雜度（Asymptotic /??simp't?tik,-k?l/ Time Complexity） 和 漸進(jìn)空間復(fù)雜度（Asymptotic Space Complexity）冤议。算法的空間復(fù)雜度計(jì)算相對(duì)容易斟薇，以下僅介紹時(shí)間復(fù)雜度师坎。
多項(xiàng)式量級(jí)復(fù)雜度
復(fù)雜度根據(jù)量級(jí)可分為 多項(xiàng)式（Polynomial /?pɑl?'nom??l/） 和 非多項(xiàng)式量級(jí)（Non-Deterministic Polynomial）恕酸，O(2n) 和 O(n!) 屬于后者。當(dāng)數(shù)據(jù)規(guī)模 n 越來越大時(shí)胯陋，非多項(xiàng)式量級(jí)算法的執(zhí)行時(shí)間會(huì)急劇增加蕊温，甚至達(dá)到無限長(zhǎng)，所以非多項(xiàng)式量級(jí)算法是不可接受的低效算法遏乔。
O(logn)
根據(jù)換底公式义矛，logab=logcb/logca，logab=1/logba盟萨，有 log3n=log32 * log2n凉翻。可以看出捻激，任意底的對(duì)數(shù)都可化為 C*log2n制轰，所以，在對(duì)數(shù)階復(fù)雜度表示法中胞谭，我們忽略對(duì)數(shù)的底垃杖，統(tǒng)一表示為 O(logn)。
O(m+n) 和 O(m*n)
如果算法的數(shù)據(jù)規(guī)模為多個(gè)變量丈屹，并且無法事先評(píng)估他們的大小调俘，那么在表示時(shí)間復(fù)雜度時(shí)要把他們?nèi)繉懗觥?/p>
最好、最壞、平均和均攤時(shí)間復(fù)雜度
// 全局變量彩库，大小為 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;
}
上面這段代碼是往數(shù)組尾插入元素司忱，并且實(shí)現(xiàn)了自動(dòng)擴(kuò)容功能皇忿。在數(shù)組未滿的情況下，直接放到數(shù)組尾即可坦仍，因此鳍烁，最好時(shí)間復(fù)雜度為 O(1)。在數(shù)組滿的情況下繁扎，需要進(jìn)行 n 次移動(dòng)幔荒，并申請(qǐng) n 個(gè)空間，因此梳玫，最壞時(shí)間復(fù)雜度是 O(n)爹梁，最壞空間復(fù)雜度是 O(n)。
再看平均時(shí)間復(fù)雜度提澎，總共有 n+1 種情況姚垃，其中數(shù)組未滿有 n 種情況，每種的概率都是 1/n+1盼忌。數(shù)組滿有 1 種情況积糯，概率也是 1/n+1，所以平均時(shí)間復(fù)雜度為 (n * 1/n+1 + 1/n+1)/n+1 = O(1)谦纱。
最后計(jì)算 均攤時(shí)間復(fù)雜度看成，首先說明其概念和適用場(chǎng)景。對(duì)某個(gè)數(shù)據(jù)結(jié)構(gòu)做一組連續(xù)操作跨嘉，大部分情況下時(shí)間復(fù)雜度都很低川慌，只有個(gè)別情況下時(shí)間復(fù)雜度比較高，并且這些操作間存在前后連貫的時(shí)序關(guān)系祠乃，此時(shí)梦重，我們便可將這組操作放在一起考慮，看能否將較高時(shí)間復(fù)雜度的那些操作耗時(shí)跳纳，平攤到其他低時(shí)間復(fù)雜度操作上忍饰，這種分析方法就叫做 攤還分析，通過攤還分析得到的時(shí)間復(fù)雜度寺庄，被稱為均攤時(shí)間復(fù)雜度艾蓝。一般情況下力崇，能夠應(yīng)用均攤時(shí)間復(fù)雜度分析的場(chǎng)合，均攤復(fù)雜度等于最好時(shí)間復(fù)雜度赢织。
對(duì)于上例亮靴，每一次 O(n) 的移動(dòng)操作，都會(huì)跟著 n 次 O(1) 的插入操作于置，所以把耗時(shí)多的那次操作均攤到接下來的 n 次耗時(shí)少的操作上茧吊，這一組連續(xù)操作的均攤時(shí)間復(fù)雜度就是 O(1)。
簡(jiǎn)要總結(jié)
最好時(shí)間復(fù)雜度計(jì)算簡(jiǎn)單八毯，與此同時(shí)搓侄，參考意義也不是很大。最壞時(shí)間復(fù)雜度計(jì)算較為復(fù)雜话速，如用于關(guān)鍵環(huán)節(jié)需要重點(diǎn)考慮讶踪。平均時(shí)間復(fù)雜度計(jì)算最為復(fù)雜，也是最常用的評(píng)價(jià)指標(biāo)泊交，而可以使用攤還分析的算法乳讥，使用均攤時(shí)間復(fù)雜度代替常規(guī)的加權(quán)平均/期望得出的平均復(fù)雜度更具實(shí)際意義。
