每個(gè)開(kāi)發(fā)者都必須知道的14個(gè)數(shù)字
Jeff Dean , 一位著名的 Google 工程師, 推出了一個(gè) 每個(gè)人都必須知道的數(shù)字 的潛在數(shù)字列表。這個(gè)列表對(duì)設(shè)計(jì)大型基礎(chǔ)架構(gòu)的系統(tǒng)是一個(gè)巨大的資源。
算法及其復(fù)雜性總是會(huì)在計(jì)算機(jī)系統(tǒng)的關(guān)鍵部分出現(xiàn)，但我發(fā)現(xiàn)很少有工程師對(duì)一個(gè)O(n!)級(jí)算法相較一個(gè) O(n5) 算法會(huì)怎樣有很好的理解。
在編碼比賽世界里，競(jìng)爭(zhēng)選手一直在考慮這些優(yōu)化權(quán)衡。毫不奇怪，有一組每個(gè)算法設(shè)計(jì)者都應(yīng)該知道的數(shù)字。
下面的表格顯示了不同復(fù)雜度算法條件下，在幾秒鐘內(nèi)它們可以達(dá)到的極限，n是輸入量大小。我已經(jīng)為每個(gè)復(fù)雜的類型增加了一些算法和數(shù)據(jù)結(jié)構(gòu)的例子。
| n最大值 | 復(fù)雜度 | 算法 | 數(shù)據(jù)結(jié)構(gòu) |
|---|---|---|---|
| 1,000,000,000 and higher | log n, sqrt n | 對(duì)分查找，三元查找， 快速指數(shù)，歐幾里得算法 | |
| 10,000,000 | n, n log log n, n log* n | 集合相交, Eratosthenes篩選法,基數(shù)排序, KMP算法,拓?fù)渑判?span>,歐拉路徑, 強(qiáng)連通分量, 2sat圖 | 不相交的集, tries樹(shù), 哈希映射, 滾動(dòng)散列雙端隊(duì)列 |
| 1,000,000 | n log n | 排序, 分治法, 掃描線算法, Kruskal算法, Dijkstra算法 | 段樹(shù), 范圍樹(shù), 堆, 二叉排序樹(shù), 樹(shù)狀數(shù)組, 后綴數(shù)組 |
| 100,000 | n log2 n | 分治法 | 2d范圍樹(shù) |
| 50,000 | n1.585, n sqrt n | Karatsuba乘法算法, 平方根技巧 | 兩層樹(shù) |
| 1000 - 10,000 | n2 | 最大空矩形, Dijkstra算法, 普里姆算法 (密集圖) | |
| 300-500 | n3 | 所有對(duì)最短路徑, 最大和子陣,原生矩陣乘法, 矩陣鏈乘積, 高斯消元法, 網(wǎng)絡(luò)流 | |
| 30-50 | n4, n5, n6 | ||
| 25 - 40 | 3n/2, 2n/2 |
中途相遇 |
哈希表 (交叉集) |
| 15 - 24 | 2n | 子集枚舉, 暴力破解, 動(dòng)態(tài)規(guī)劃與指數(shù)狀態(tài) | |
| 15 - 20 | n2 2n | 動(dòng)態(tài)規(guī)劃與指數(shù)狀態(tài) | 位集合, 哈希映射 |
| 13-17 | 3n | 動(dòng)態(tài)規(guī)劃與指數(shù)狀態(tài) | 哈希映射 (保存狀態(tài)) |
| 11 | n! | 暴力破解,回溯法, next_permutation全排列 | |
| 8 | nn | 暴力破解, 笛卡爾積 |
這些數(shù)字不是非常精確，它們假設(shè)了內(nèi)存操作以及一些變化的常數(shù)因子，但對(duì)于找到與你的問(wèn)題和數(shù)據(jù)量大小相適應(yīng)的解決方案研究方面，它們確實(shí)給出了一個(gè)很好的起點(diǎn)。
讓我們通過(guò)一個(gè)實(shí)例來(lái)繼續(xù)講解。
假設(shè)你為一家GPS公司工作，你的項(xiàng)目是改善他們的導(dǎo)航功能。在學(xué)校，你學(xué)會(huì)使用Dijkstra's 算法，在圖上計(jì)算兩點(diǎn)之間的最短距離。了解這些數(shù)字，你就會(huì)明白，他將耗費(fèi)幾秒鐘以計(jì)算具有上百萬(wàn)條邊的圖形，Dijkstra's 算法實(shí)現(xiàn)這些，有的時(shí)間復(fù)雜度（m代表邊數(shù)，n表示節(jié)點(diǎn)數(shù)）。
現(xiàn)在你面臨一個(gè)新的問(wèn)題：
你期望你的代碼能執(zhí)行多塊？幾秒鐘？數(shù)百毫秒？
如果它在網(wǎng)絡(luò)上的響應(yīng)時(shí)間少于500毫秒，就覺(jué)得快。因此我們選半秒。
圖有多大？你想解決問(wèn)題是一個(gè)城市，一個(gè)國(guó)家還是一片大陸？
每一個(gè)大于其他大小的，將通過(guò)不同的方法解決。
比方說(shuō)，我們要解決整個(gè)歐洲的問(wèn)題。
下面是一些輸入集的大?。?/p>
即使我們選擇半秒時(shí)間作為我們的執(zhí)行時(shí)間，我們選的問(wèn)題大小大約是4千萬(wàn)條邊數(shù)，從我們提供的表里哼清楚地看到， m log n 太慢了。因此純Dijkstra 算法解決不了我們的問(wèn)題。我們需要卡看別的算法，如A星搜索算法或者基于 對(duì)于這個(gè)問(wèn)題的高速公路層次式的表現(xiàn)。
原文鏈接：http://www.oschina.net/translate/numbers-everyone-should-know
