關(guān)于算法時(shí)間復(fù)雜度的例子
O(1)
數(shù)組中取出[i]位置元素，哈希表取出元素。通常哈希表比數(shù)組尋址慢很多。
計(jì)算+-*/運(yùn)算以及位運(yùn)算。位運(yùn)算一般最快。
乘方慢很多，但也可以當(dāng)成O1
集合中查找元素是否存在，插入元素，刪除元素。
鏈表刪除元素、雙向鏈表刪除節(jié)點(diǎn)
通過(guò)數(shù)學(xué)公式求得一個(gè)結(jié)果，前n項(xiàng)和公式，xxxx通項(xiàng)公式。
O(logn)
二分查找
二叉查找樹(shù)、平衡二叉樹(shù)查找，插入元素、刪除元素。
堆彈出一個(gè)元素，最后一個(gè)元素彌補(bǔ)上來(lái)然后下沉到底。堆插入一個(gè)元素，插如到堆右下角，一路往上竄。
快速排序空間復(fù)雜度，壓棧就是樹(shù)的最大高度。
通常對(duì)二叉樹(shù)進(jìn)行dfs的空間復(fù)雜度。
快速冪，自身迭代快速到達(dá)指定的數(shù)字。
gcd 歐幾里得的輾轉(zhuǎn)相除
O(n^0.5)
判斷一個(gè)數(shù)是否是質(zhì)數(shù)，只需要從1判斷到根號(hào)下他自己就可以了。有待證明。
一些不常見(jiàn)的特殊的數(shù)學(xué)題目。
O(n log log n)
素?cái)?shù)篩
歐拉篩
O(n)
遍歷數(shù)組：順序查找、參數(shù)是數(shù)組的max、min函數(shù)
桶排序
字符串生成Counter哈希表
借助輔助數(shù)組的空間復(fù)雜度，歸并排序。
kmp算法生成next數(shù)組，以及匹配。
O(nlogn)
對(duì)長(zhǎng)度為n的數(shù)組進(jìn)行高效的排序：經(jīng)典三大nlogN級(jí)別：快排，堆排，歸并。
貪心題目的時(shí)間復(fù)雜度多為此。因?yàn)橥ǔＰ枰判颉?/span>
克魯斯卡爾根據(jù)圖的邊生成最小生成樹(shù)，邊的數(shù)量N，時(shí)間復(fù)雜度NlogN。
O(n^2)
低效率的排序：冒泡排序、選擇排序
排序的最差情況：插入排序最差情況。不帶隨機(jī)效果的快速排序最差情況
遍歷所有二元對(duì)：數(shù)據(jù)兩兩比較
普里姆的最小生成樹(shù)算法。節(jié)點(diǎn)為n
二維dp填表，網(wǎng)格路徑問(wèn)題，兩個(gè)數(shù)組的最長(zhǎng)公共子序列問(wèn)題dp解
O(n^3)
遍歷3D世界所有方塊，就是三維數(shù)組
三維dp。dp問(wèn)題的時(shí)間復(fù)雜度一般都是多項(xiàng)式級(jí)別。不會(huì)成為指數(shù)級(jí)別。
O(2^n)
糟糕的遞歸：斐波那契，漢諾塔
O(n!)
全排列的所有可能
猴子排序的可能時(shí)間復(fù)雜度
補(bǔ)充：Stirling公式
O(n^n)
和上一個(gè)是等價(jià)無(wú)窮大
