每个开发者都必须知道的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 log² n	分治法	2d范围树
50,000	n^1.585, n sqrt n	Karatsuba乘法算法, 平方根技巧	两层树
1000 - 10,000	n²	最大空矩形, Dijkstra算法, 普里姆算法 (密集图)
300-500	n³	所有对最短路径, 最大和子阵,原生矩阵乘法, 矩阵链乘积, 高斯消元法, 网络流
30-50	n⁴, n⁵, n⁶
25 - 40	3^n/2, 2^n/2	中途相遇	哈希表 (交叉集)
15 - 24	2ⁿ	子集枚举, 暴力破解, 动态规划与指数状态
15 - 20	n² 2ⁿ	动态规划与指数状态	位集合, 哈希映射
13-17	3ⁿ	动态规划与指数状态	哈希映射 (保存状态)
11	n!	暴力破解,回溯法, next_permutation全排列
8	nⁿ	暴力破解, 笛卡尔积

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

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

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

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

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

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

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

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

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

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

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

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容