【百科】怎样判断算法效率高不高-新东方前途出国

怎样判断算法效率高不高

算法是一套通过确定性保证解决问题的工具。可在现实中，你会发现算法工程师格外关注效率。当我们把问题交给算法，不只关心能不能解决，还关心多久能解决。  

比起让人类处理问题，我们给算法的耐心总是特别少。你用1小时去图书馆书架上找几本书，不觉得浪费时间。可搜索一个关键词，谷歌1小时后出结果，那就受不了了。当打网约车的时候，多等的每一分钟，都让顾客在取消订单的边缘疯狂试探。  

人们对效率的高期待，迫使算法工程师不断提高算法效率。

 

谷歌平均每年要接待2兆次搜索，也就是每秒钟大约要进行七万次搜索。如果没有非常高效率的算法，谷歌是不可能支撑这么庞大的业务的。  

那算法工程师是怎么提高效率的呢？要回答这个问题，我们得先往后退一步，搞懂算法效率是怎么评价的。不能评价算法效率的高低，就谈不上提高效率。  

1. 评价算法效率的两个难题  

为什么要专门说算法效率的评价呢？  

因为它跟我们平时评价效率的方式不一样。我们一般说效率，说的就是完成任务的时间。但用绝对时间在算法领域却不是很适用。

 

咱们拿赛车举个例子。设想F1方程式赛车中，两位最著名的赛车手，舒马赫和汉密尔顿一起跑上海赛道，怎么分胜负？谁先跑完，用时短，就获胜。

 

但我们却没办法用这样的方式来评价算法。求解同一个问题，50年前可能要算1个月，现在3秒就算出来了，能说现在的算法效率更高吗？50年前和现在，算法可能是一样的，速度提升是因为硬件提升了。  

这就像是，舒马赫开夏利，一个货车司机开法拉利，跑同一个赛道，货车司机赢了，就能说他比舒马赫驾驶技术更高超吗？  

这是算法效率评价的第一个难题——“硬件依赖”。除了硬件依赖，还有第二个难题，我管它叫“无穷大”的难题。  

当算法的输入规模，趋近于无穷大的时候，算法解决问题所花的时间也趋近于无穷大。也就是说，当舒马赫和货车司机，开着不同的赛车，在上海赛道上跑100圈，或者1000圈。随着圈数增加，完成比赛的总时间趋近于无穷大，用绝对时间就没法比较了。

 

面对这两个难题，我们需要另一种度量算法效率的工具。既能比较不同算法之间的效率高低，还不需要依赖于计算机的硬件水平。这个度量工具，叫作“时间复杂度”。  

2. 时间复杂度是度量算法效率最主要的工具  

什么是时间复杂度呢？教科书说，时间复杂度是算法中某些基本操作的总数量，随着算法输入的规模而增长的函数关系。

 

这句话很绕，把三个关键词提炼出来，就是“基本操作的总数量”“输入规模”以及“函数关系”。  

拿盖金字塔打个比方，来理解一下这三个关键概念。假如有一天，法老抓来两个工匠给他盖金字塔，一个叫阿蒙，一个叫迪尔，谁效率低就处死谁。阿蒙1天能垒1块石头，迪尔3天才垒1块。不用说，迪尔不好好干，他肯定要被处死。  

但增加一个条件，结果立马就变了。刚才法老抓俩工匠的时候，还没画图纸，只说要盖一座10米高的金字塔，设计图纸你们自己看着办。阿蒙画了一个图纸，需要用50万块石头，迪尔只要10万块石头就能盖完金字塔，你说这回该处死谁呢？恐怕是阿蒙了。  

如果把算法比喻成盖金字塔，垒石头就是算法的“基本操作”，金字塔的高度相当于“输入规模”，而他们的图纸就是垒石块总量，跟盖金字塔高度之间的函数关系，这就是时间复杂度。

 

算法工程师扮演的就是法老的角色，关注的就是哪个算法的“图纸”更高明。当“输入规模”增加，你要盖的不再是10米的金字塔，而是100米、1000米的时候，比起垒一块石头的效率，图纸变得重要得多。而算法工程师的工作就是找到更好的“图纸”，找到效率更高、时间复杂度更低的算法。  

3. 降低时间复杂度方法一：空间换时间  

我们用时间复杂度来评价算法效率，那么要提高算法效率，就要想办法降低时间复杂度。怎么做呢？我先来给你介绍两种常用的办法。  

先来说第一个，空间换时间。这里要说一个新的概念，叫作“空间复杂度”，也是衡量算法效率的一个标准。不过，“千金难买寸光阴”，在实际中，我们经常会用牺牲空间复杂度的方式，降低时间复杂度，就是所谓的“空间换时间”。

 

什么是空间复杂度呢？和时间复杂度差不多，也是一种函数关系。是算法占据的空间资源，随着输入规模变大而增长的函数关系。  

举个例子，计算机普及之前，你去图书馆借书要用一种叫索引卡的工具。图书管理员会根据索引卡的信息帮你找书。  

如果把这个事件看作是算法过程，输入就是你想要的书名，输出是你想要的书籍。这个算法不只需要有人帮你找书，还需要有大量书籍、放书的书架以及索引卡等工具。我们需要物理硬件支持，这就是图书馆，它们都要占据空间。  

不管谁来借书，图书、书架包括索引卡都要占用固定的空间，占了就是占了，不能用来干别的。这就是我们的硬盘空间。而图书管理员，每次取书回来之后，他就可以休息或者干些其他工作。他占用的空间是可以释放的。这就对应计算机中的内存空间。  

所以空间复杂度的概念就是衡量不同算法在运算的时候，需要占据空间资源的大小。有意思的是，在计算机里空间和时间是可以互换的。  

为什么图书馆里要给书建索引呢？如果不建索引卡，索引卡占据的空间是“零”，只是找书会相当艰难，完全靠图书管理员在浩瀚的书当中寻找。这种算法的空间复杂度虽然低，但时间复杂度非常高。  

但如果给每本书都建立索引，管理员找书的时间很短，但占的空间就大。而且书越多，索引卡占的空间就越大。不过，面对时间复杂度，牺牲一些存储空间，换来更快的搜索速度一定是非常划算的。  

4. 降低时间复杂度的方法二：分治思想  

除了利用空间资源来降低时间复杂度，改进算法，同样可以降低时间复杂度。不少算法策略可以帮助实现这个目的，比如分治思想。这就是要讲的第二种降低时间复杂度的方法。

 

还是举个例子，现在下载一首歌曲，几秒钟就能搞定。  

为什么能那么快呢？这背后源于一个伟大的算法——快速傅立叶变换。  

我们听到的声音是以波的形式存在的。不过，以波的形式存储的音频占的空间太大，网络传递太慢。所以要先压缩，把波的形式转换成频率的形式，占的空间会变小，传播起来也就更快。  

而这个转换的过程，使用的算法就是傅立叶变换。  

可惜，这个算法并不快，压缩一个5分钟的音频可能需要1天。为了加速这个变换，1965年，美国数学家库利和图基采用“分治”的思想，发明了快速傅立叶变换，把时间复杂度降了一个量级。现在，我们压缩一个5分钟的音频连1秒的时间都不需要，时间复杂度带来的差别就是那么大。  

划重点  

1. 时间复杂度是工具，可以衡量、比较不同算法的效率。  

2. 时间复杂度也是一种指标，能够督促算法工程师不断改进算法，降低复杂度，提高效率。  

3. 想要降低时间复杂度，我们可以用“空间换时间”和“分治”的办法。

 

【免责声明】

1、个别文章内容来源于网络善意转载，版权归原作者所有，如侵权，请联系删除；

2、所有图片来源于网络，版权归原作者所有。如有侵权问题请告知，我们会立即处理。