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

Send_linux

　　
   
        
            
            
            
下面的表格显示了不同复杂度算法条件下，在几秒钟内它们可以达到的极限，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毫秒，就觉得快。因此我们选半秒。
            
图有多大？你想解决问题是一个城市，一个国家还是一片大陆？
            
            
        
   
   
        
            
            
            
每一个大于其他大小的，将通过不同的方法解决。
            
比方说，我们要解决整个欧洲的问题。
            
下面是一些输入集的大小：
            
               
                    
                        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星搜索算法或者基于 对于这个问题的高速公路层次式的表现。
            
            
        
   
英文原文：
14 numbers every developer should know
                       
                               
                    
                               
                       
                       
                       
                                时间:2013-03-31 09:02来源:开源中国社区 作者:zhangkai责任编辑:zhangkai

本文来自ChinaUnix新闻频道，如果查看原文请点：http://news.chinaunix.net/opensource/2013/0331/2700433.shtml