關(guān)于算法時(shí)間復(fù)雜度的例子

O(1)

1. 數(shù)組中取出[i]位置元素，哈希表取出元素。通常哈希表比數(shù)組尋址慢很多。

2. 計(jì)算+-*/運(yùn)算以及位運(yùn)算。位運(yùn)算一般最快。

3. 乘方慢很多，但也可以當(dāng)成O1

4. 集合中查找元素是否存在，插入元素，刪除元素。

5. 鏈表刪除元素、雙向鏈表刪除節(jié)點(diǎn)

6. 通過(guò)數(shù)學(xué)公式求得一個(gè)結(jié)果，前n項(xiàng)和公式，xxxx通項(xiàng)公式。

O(logn)

1. 二分查找

2. 二叉查找樹(shù)、平衡二叉樹(shù)查找，插入元素、刪除元素。

3. 堆彈出一個(gè)元素，最后一個(gè)元素彌補(bǔ)上來(lái)然后下沉到底。堆插入一個(gè)元素，插如到堆右下角，一路往上竄。

4. 快速排序空間復(fù)雜度，壓棧就是樹(shù)的最大高度。

5. 通常對(duì)二叉樹(shù)進(jìn)行dfs的空間復(fù)雜度。

6. 快速冪，自身迭代快速到達(dá)指定的數(shù)字。

7. gcd 歐幾里得的輾轉(zhuǎn)相除

O(n^0.5)

1. 判斷一個(gè)數(shù)是否是質(zhì)數(shù)，只需要從1判斷到根號(hào)下他自己就可以了。有待證明。

2. 一些不常見(jiàn)的特殊的數(shù)學(xué)題目。

O(n log log n)

1. 素?cái)?shù)篩

2. 歐拉篩

O(n)

1. 遍歷數(shù)組：順序查找、參數(shù)是數(shù)組的max、min函數(shù)

2. 桶排序

3. 字符串生成Counter哈希表

4. 借助輔助數(shù)組的空間復(fù)雜度，歸并排序。

5. kmp算法生成next數(shù)組，以及匹配。

O(nlogn)

1. 對(duì)長(zhǎng)度為n的數(shù)組進(jìn)行高效的排序：經(jīng)典三大nlogN級(jí)別：快排，堆排，歸并。

2. 貪心題目的時(shí)間復(fù)雜度多為此。因?yàn)橥ǔＰ枰判颉?/span>

3. 克魯斯卡爾根據(jù)圖的邊生成最小生成樹(shù)，邊的數(shù)量N，時(shí)間復(fù)雜度NlogN。

O(n^2)

1. 低效率的排序：冒泡排序、選擇排序

2. 排序的最差情況：插入排序最差情況。不帶隨機(jī)效果的快速排序最差情況

3. 遍歷所有二元對(duì)：數(shù)據(jù)兩兩比較

4. 普里姆的最小生成樹(shù)算法。節(jié)點(diǎn)為n

5. 二維dp填表，網(wǎng)格路徑問(wèn)題，兩個(gè)數(shù)組的最長(zhǎng)公共子序列問(wèn)題dp解

O(n^3)

1. 遍歷3D世界所有方塊，就是三維數(shù)組

2. 三維dp。dp問(wèn)題的時(shí)間復(fù)雜度一般都是多項(xiàng)式級(jí)別。不會(huì)成為指數(shù)級(jí)別。

O(2^n)

1. 糟糕的遞歸：斐波那契，漢諾塔

O(n!)

1. 全排列的所有可能

2. 猴子排序的可能時(shí)間復(fù)雜度

補(bǔ)充：Stirling公式

O(n^n)

和上一個(gè)是等價(jià)無(wú)窮大

1. 決策樹(shù)的深度成為了變量n，分叉數(shù)量也成了變量n。