知道算法有多快以及需要多少空間是非常有用的迫卢。 才能為你的工作選擇正確的算法哮肚。
O表示法給你一個(gè)算法的運(yùn)行時(shí)間和它使用的內(nèi)存量的粗略表示雅倒。 當(dāng)有人說绅络，“這種算法最糟糕的運(yùn)行時(shí)間是O（n ^ 2），使用O（n）空間”狈茉。意思是它很慢夫椭，但不需要大量額外的內(nèi)存。
計(jì)算算法的O通常通過數(shù)學(xué)分析來完成氯庆。 我們跳過這里的數(shù)學(xué)蹭秋，但是了解不同的值意味著什么是有用的，所以這里是一個(gè)方便查閱的表堤撵。 n指您正在處理的數(shù)據(jù)項(xiàng)數(shù)仁讨。 例如，當(dāng)對(duì)100個(gè)項(xiàng)目的數(shù)組進(jìn)行排序時(shí)实昨，n = 100洞豁。
| 大O | ?名字 | ?說明 |
|---|---|---|
| O(1) | ?常量 | 這是最好的。 該算法不管有多少數(shù)據(jù)荒给，總是花費(fèi)相同的時(shí)間丈挟。 示例：通過索引查找數(shù)組的元素。 |
| O(log n) | 對(duì)數(shù) | 特別好志电。 該算法將每次迭代的數(shù)據(jù)量減半曙咽。 如果你有100個(gè)元素，它需要大約7個(gè)步驟來找到答案溪北。 有1000個(gè)，需要10個(gè)步驟夺脾。 100萬個(gè)只需要20步之拨。 即使對(duì)于大量的數(shù)據(jù)，這也是超快的咧叭。 示例：二進(jìn)制搜索蚀乔。 |
| O(n) | 線性 | 很好。 如果你有100個(gè)元素菲茬，需要100個(gè)步驟吉挣。 元素個(gè)數(shù)增加一倍派撕，該算法花費(fèi)的時(shí)間會(huì)是兩倍。 示例：順序搜索睬魂。 |
| O(n log n) | 線性代數(shù) | 體面的表現(xiàn)终吼。 這比線性稍差，但不太差氯哮。 示例：最快的通用排序算法际跪。 |
| O(n^2) | 二次 | 有點(diǎn)慢。 如果你有100個(gè)元素喉钢，要執(zhí)行100 ^ 2 = 10,000步驟姆打。 加倍的元素?cái)?shù)量使其慢四倍（因?yàn)?平方等于4）。 示例：使用嵌套循環(huán)的算法肠虽，如插入排序幔戏。 |
| O(n^3) | ?三次 | 很慢。 如果你有100元素税课，會(huì)是100 ^ 3 = 1,000,000步驟闲延。 輸入大小加倍使其慢8倍。 示例：矩陣乘法伯复。 |
| O(2^n) | 指數(shù) | 特別慢。 你想避免這些算法啸如，但有時(shí)你沒有選擇。 添加一個(gè)元素就會(huì)使運(yùn)行時(shí)間加倍想暗。 示例：旅行推銷員問題 |
| O(n!) | 階乘 | 無法忍受的慢。 一百萬年也運(yùn)行不完帘不。 |
通常你不需要數(shù)學(xué)方式計(jì)算一個(gè)算法的?大O说莫，但你可以簡(jiǎn)單地使用你的直覺。 如果你的代碼使用一個(gè)循環(huán)寞焙，看看你的輸入的所有n個(gè)元素储狭，算法是 O(n) 。 如果代碼有兩個(gè)嵌套循環(huán)捣郊，它是 O(n ^ 2) 辽狈。 三個(gè)嵌套循環(huán)給出 O(n ^ 3) ，等等呛牲。
上面的表示法是一個(gè)估計(jì)刮萌，只對(duì)較大數(shù)量的元素真正有用。 例如娘扩，插入排序算法的最壞情況運(yùn)行時(shí)間是 O(n ^ 2) 壮锻。 在理論上比合并排序的最壞情況運(yùn)行時(shí)間是 O(n log n) 。 但對(duì)于少量的數(shù)據(jù)涮阔，插入排序?qū)嶋H上更快澎语，特別是如果數(shù)組的一部分已經(jīng)排序途事！
如果你覺得這個(gè)很混亂擅羞，不要讓這個(gè)表格打擾你太多尸变。 當(dāng)比較兩個(gè)算法以確定哪一個(gè)更好時(shí)，它是最有用的减俏。 但是最終你還是想在實(shí)踐中測(cè)試哪一個(gè)真正是最好的召烂。 如果數(shù)據(jù)量相對(duì)較小娃承，即使緩慢的算法在實(shí)際運(yùn)行中也很快。
