复杂度分析上如何统计算法执行效率资源消耗.pdfVIP

03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？

2018-09-26

03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？

朗读人：修阳19′42′′|9.04M

我们都知道，数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代

码更省空间。所以，执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代

码的执行效率呢？这里就要用到我们今天要讲的内容：时间、空间复杂度分析。

其实，只要讲到数据结构与算法，就一定离不开时间、空间复杂度分析。而且，我个人认为，复杂

度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。

复杂度分析实在太重要了，因此我准备用两节内容来讲。希望你学完这个内容，无论在任何场

景下，面对任何代码的复杂度分析，你都能做到“庖丁解牛”般游刃有余。

为什么需要复杂度分析？

你可能会有些疑惑，我把代码跑一遍，通过统计、，就能得到算法执行的时间和占用的内存大

小。为什么还要做时间、空间复杂度分析呢？这种分析方法能比我实实在在跑一遍得到的数据更准

确吗？

首先，我可以肯定地说，你这种评估算法执行效率的方法是正确的。很多数据结构和算法书籍还给

这种方法起了一个名字，叫事后统计法。但是，这种统计方法有非常大的局限性。

1.测试结果非常依赖测试环境

测试环境中硬件的不同会对测试结果有很大的影响。比如，我们拿同样一段代码，分别用IntelCore

i9处理器和IntelCorei3处理器来运行，不用说，i9处理器要比i3处理器执行的速度快很多。还

有，比如原本在这台机器上a代码执行的速度比b代码要快，等我们换到另一台机器上时，可能会

有截然相反的结果。

2.测试结果受数据规模的影响很大

后面我们会讲排序算法，我们先拿它举个例子。对同一个排序算法，待排序数据的有序度不一样，

排序的执行时间就会有很大的差别。情况下，如果数据已经是有序的，那排序算法不需要做任

何操作，执行时间就会非常短。除此之外，如果测试数据规模太小，测试结果可能无法反应

算法的性能。比如，对于小规模的数据排序，排序可能反倒会比快速排序要快！

所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。这就

是我们今天要讲的时间、空间复杂度分析方法。

大O复杂度表示法

算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉

眼”得到一段代码的执行时间呢？

这里有段非常简单的代码，求1,2,3…n的累加和。现在，我就带你一块来估算一下这段代码的执行

时间。

代码

intcal(intn){

intsum0;

inti=1;

for(;i=n;++i)

{sum=sum+i;

}

returnsum;

}

从CPU的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。尽管每行代码

对应的CPU执行的个数、执行的时间都不一样，但是，我们这里只是粗略估计，所以可以假设每

行代码执行的时间都一样，为unit_time。在这个假设的基础之上，这段代码的总执行时间是多少

呢？

第