每个开发者都必须知道的14个数字

2013-3-31 12:26| 发布者: joejoe0332| 查看: 1477| 评论: 0|原作者: 开源中国社区|来自: 开源中国社区

摘要: 　　下面的表格显示了不同复杂度算法条件下，在几秒钟内它们可以达到的极限，n是输入量大小。我已经为每个复杂的类型增加了一些算法和数据结构的例子。 n最大值复杂度算法数据结构 1,000,000,000 and higher ...

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