开源中国

我们不支持 IE 10 及以下版本浏览器

It appears you’re using an unsupported browser

为了获得更好的浏览体验,我们强烈建议您使用较新版本的 Chrome、 Firefox、 Safari 等,或者升级到最新版本的IE浏览器。 如果您使用的是 IE 11 或以上版本,请关闭“兼容性视图”。
每个开发者都必须知道的 14 个数字 - 技术翻译 - 开源中国社区

每个开发者都必须知道的 14 个数字 【已翻译100%】

标签: <无>
oschina 推荐于 5年前 (共 4 段, 翻译完成于 03-29) 评论 6
收藏  
150
推荐标签: 待读

Jeff Dean , 一位著名的 Google 工程师, 推出了一个 每个人都必须知道的数字 的潜在数字列表。这个列表对设计大型基础架构的系统是一个巨大的资源。

算法及其复杂性总是会在计算机系统的关键部分出现,但我发现很少有工程师对一个O(n!)级算法相较一个 O(n5) 算法会怎样有很好的理解。

在编码比赛世界里,竞争选手一直在考虑这些优化权衡。毫不奇怪,有一组每个算法设计者都应该知道的数字。

super0555
 翻译得不错哦!

下面的表格显示了不同复杂度算法条件下,在几秒钟内它们可以达到的极限,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 暴力破解, 笛卡尔积  


这些数字不是非常精确,它们假设了内存操作以及一些变化的常数因子,但对于找到与你的问题和数据量大小相适应的解决方案研究方面,它们确实给出了一个很好的起点。 

super0555
 翻译得不错哦!

让我们通过一个实例来继续讲解。

假设你为一家GPS公司工作,你的项目是改善他们的导航功能。在学校,你学会使用Dijkstra's 算法,在图上计算两点之间的最短距离。了解这些数字,你就会明白,他将耗费几秒钟以计算具有上百万条边的图形,Dijkstra's 算法实现这些,有的时间复杂度(m代表边数,n表示节点数)。

现在你面临一个新的问题:

你期望你的代码能执行多块?几秒钟?数百毫秒?

如果它在网络上的响应时间少于500毫秒,就觉得快。因此我们选半秒。

图有多大?你想解决问题是一个城市,一个国家还是一片大陆?

等PM
 翻译得不错哦!

每一个大于其他大小的,将通过不同的方法解决。

比方说,我们要解决整个欧洲的问题。

下面是一些输入集的大小:

input Europe USA/CAN USA (Tiger)
#nodes 18 029 721 18 741 705 24 278 285
#directed edges 42 199 587 47 244 849 58 213 192
#road categories 13 13 4


即使我们选择半秒时间作为我们的执行时间,我们选的问题大小大约是4千万条边数,从我们提供的表里哼清楚地看到, m log n 太慢了。因此纯Dijkstra 算法解决不了我们的问题。我们需要卡看别的算法,如A星搜索算法或者基于 对于这个问题的高速公路层次式的表现。

等PM
 翻译得不错哦!
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们
评论(6)
Ctrl/CMD+Enter

专有名词太多鸟!55~不过是一篇好文!
动态规划时间复杂度很多是线性的把,哪有2^n那么慢

引用来自“牧马”的评论

动态规划时间复杂度很多是线性的把,哪有2^n那么慢

可能是从悲观考虑的吧

引用来自“牧马”的评论

动态规划时间复杂度很多是线性的把,哪有2^n那么慢

这个要看怎么设计的状态,如果状态数是指数级,那也没有办法

引用来自“Frank_mc”的评论

引用来自“牧马”的评论

动态规划时间复杂度很多是线性的把,哪有2^n那么慢

这个要看怎么设计的状态,如果状态数是指数级,那也没有办法

NP问题没有线性解法也怪不了DP噻
http://bigocheatsheet.com/《Know Thy Complexities!》这个也很不错!分享了
顶部