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