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