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

03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ 03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ “ ” “ ” 我们都知道，数据结构和算法本身解决的是 快 和 省 的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量 指标。那如何来衡量你编写的算法代码的执行效率呢？这里就要用到我们今天要讲的内容：时间、空间复杂度分析。 其实，只要讲到数据结构与算法，就一定离不开时间、空间复杂度分析。而且，我个人认为，复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算 法的内容基本上就掌握了一半。 “ ” 复杂度分析实在太重要了，因此我准备用两节内容来讲。希望你学完这个内容之后，无论在任何场景下，面对任何代码的复杂度分析，你都能做到 庖丁解牛 般 游刃有余。 为什么需要复杂度分析？ 你可能会有些疑惑，我把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？这种分析方法能 比我实实在在跑一遍得到的数据更准确吗？ 首先，我可以肯定地说，你这种评估算法执行效率的方法是正确的。很多数据结构和算法书籍还给这种方法起了一个名字，叫事后统计法。但是，这种统计方法 有非常大的局限性。 1. 测试结果非常依赖测试环境 Intel Core i9 Intel Core i3 i9 测试环境中硬件的不同会对测试结果有很大的影响。比如，我们拿同样一段代码，分别用 处理器和 处理器来运行，不用说， 处理器要 i3 a b 比 处理器执行的速度快很多。还有，比如原本在这台机器上 代码执行的速度比 代码要快，等我们换到另一台机器上时，可能会有截然相反的结果。 2.测试结果受数据规模的影响很大 后面我们会讲排序算法，我们先拿它举个例子。对同一个排序算法，待排序数据的有序度不一样，排序的执行时间就会有很大的差别。极端情况下，如果数据已 经是有序的，那排序算法不需要做任何操作，执行时间就会非常短。除此之外，如果测试数据规模太小，测试结果可能无法真实地反应算法的性能。比如，对于 小规模的数据排序，插入排序可能反倒会比快速排序要快！ 所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。这就是我们今天要讲的时间、空间复杂度分析方法。 O 大 复杂度表示法 “ ” 算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用 肉眼 得到一段代码的执行时间呢？ 这里有段非常简单的代码，求1,2,3…n的累加和。现在，我就带你一块来估算一下这段代码的执行时间。 int cal(int n) { int sum = 0; int i = 1; for (; i = n; ++i) { sum = sum + i; } return sum; file:///F/temp/geektime/数据结构与算法之美/03复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？.html[2019/1/15 15:35:11] 03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ } 从