《03复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？.pdf》由会员分享，可在线阅读，更多相关《03复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？.pdf（12页珍藏版）》请在三一文库上搜索。
1、03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ file:/F/temp/geektime/数据结构与算法之美/03复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？.html2019/1/15 15:35:11 03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ 我们都知道，数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量 指标。那如何来衡量你编写的算法代码的执行效率呢？这里就要用到我们今天要讲的内容：时间、空间复杂度分析。 其实，只要讲到数据结构与算法，就一定离不开
2、时间、空间复杂度分析。而且，我个人认为，复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算 法的内容基本上就掌握了一半。 复杂度分析实在太重要了，因此我准备用两节内容来讲。希望你学完这个内容之后，无论在任何场景下，面对任何代码的复杂度分析，你都能做到“庖丁解牛”般 游刃有余。 为什么需要复杂度分析？ 你可能会有些疑惑，我把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？这种分析方法能 比我实实在在跑一遍得到的数据更准确吗？ 首先，我可以肯定地说，你这种评估算法执行效率的方法是正确的。很多数据结构和算法书籍还给这种方法起了一个名字，
3、叫事后统计法。但是，这种统计方法 有非常大的局限性。 1. 测试结果非常依赖测试环境 测试环境中硬件的不同会对测试结果有很大的影响。比如，我们拿同样一段代码，分别用Intel Core i9处理器和Intel Core i3处理器来运行，不用说，i9处理器要 比i3处理器执行的速度快很多。还有，比如原本在这台机器上a代码执行的速度比b代码要快，等我们换到另一台机器上时，可能会有截然相反的结果。 2.测试结果受数据规模的影响很大 后面我们会讲排序算法，我们先拿它举个例子。对同一个排序算法，待排序数据的有序度不一样，排序的执行时间就会有很大的差别。极端情况下，如果数据已 经是有序的，那排序算法不需
4、要做任何操作，执行时间就会非常短。除此之外，如果测试数据规模太小，测试结果可能无法真实地反应算法的性能。比如，对于 小规模的数据排序，插入排序可能反倒会比快速排序要快！ 所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。这就是我们今天要讲的时间、空间复杂度分析方法。 大O复杂度表示法 算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？ 这里有段非常简单的代码，求1,2,3n的累加和。现在，我就带你一块来估算一下这段代码的执行时间。 int cal(int n) int sum = 0; int
5、i = 1; for (; i = 0; -i) print out ai 跟时间复杂度分析一样，我们可以看到，第2行代码中，我们申请了一个空间存储变量i，但是它是常量阶的，跟数据规模n没有关系，所以我们可以忽略。第3行申 请了一个大小为n的int类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是O(n)。 我们常见的空间复杂度就是O(1)、O(n)、O(n2 )，像O(logn)、O(nlogn)这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。 所以，对于空间复杂度，掌握刚我说的这些内容已经足够了。 内容小结 03|复杂度分析（上
6、）：如何分析、统计算法的执行效率和资源消耗？ file:/F/temp/geektime/数据结构与算法之美/03复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？.html2019/1/15 15:35:11 基础复杂度分析的知识到此就讲完了，我们来总结一下。 复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率 越低。常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )。等你学完整个专栏之后，你就会发现几乎所有的数据结构和算法的复杂 度都跑不出这
7、几个。 复杂度分析并不难，关键在于多练。 之后讲后面的内容时，我还会带你详细地分析每一种数据结构和算法的时间、空间复杂度。只要跟着我的思路学习、练习， 你很快就能和我一样，每次看到代码的时候，简单的一眼就能看出其复杂度，难的稍微分析一下就能得出答案。 03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ file:/F/temp/geektime/数据结构与算法之美/03复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？.html2019/1/15 15:35:11 课后思考 有人说，我们项目之前都会进行性能测试，再做代码的时间复杂度、空间复杂度分析，是不是多此一举呢？而且
8、，每段代码都分析一下时间复杂度、空间复杂 度，是不是很浪费时间呢？你怎么看待这个问题呢？ 欢迎留言和我分享，我会第一时间给你反馈。 03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ file:/F/temp/geektime/数据结构与算法之美/03复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？.html2019/1/15 15:35:11 精选留言： xr 2018-09-25 17:50:21 我不认为是多此一举，渐进时间，空间复杂度分析为我们提供了一个很好的理论分析的方向，并且它是宿主平台无关的，能够让我们对我们的程序或算法有 一个大致的认识，让我们知道，比如
9、在最坏的情况下程序的执行效率如何，同时也为我们交流提供了一个不错的桥梁，我们可以说，算法1的时间复杂度是O (n)，算法2的时间复杂度是O(logN)，这样我们立刻就对不同的算法有了一个“效率”上的感性认识。 当然，渐进式时间，空间复杂度分析只是一个理论模型，只能提供给粗略的估计分析，我们不能直接断定就觉得O(logN)的算法一定优于O(n), 针对不同的宿 主环境，不同的数据集，不同的数据量的大小，在实际应用上面可能真正的性能会不同，个人觉得，针对不同的实际情况，进而进行一定的性能基准测试是 很有必要的，比如在统一一批手机上(同样的硬件，系统等等)进行横向基准测试，进而选择适合特定应用场景下
10、的最有算法。 综上所述，渐进式时间，空间复杂度分析与性能基准测试并不冲突，而是相辅相成的，但是一个低阶的时间复杂度程序有极大的可能性会优于一个高阶的时 间复杂度程序，所以在实际编程中，时刻关心理论时间，空间度模型是有助于产出效率高的程序的，同时，因为渐进式时间，空间复杂度分析只是提供一个 粗略的分析模型，因此也不会浪费太多时间，重点在于在编程时，要具有这种复杂度分析的思维。 584赞 作者回复2018-09-25 23:11:41 写得很好。理解的到位 姜威 2018-09-26 00:30:09 总结 一、什么是复杂度分析？ 1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题
11、”。 2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。 3.分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。 4.复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。 二、为什么要进行复杂度分析？ 1.和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。 2.掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。 三、如何进行复杂度分析？ 1.大O表示法 1）来源 算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n)表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行
12、总次数，而n往往表示数据的规 模。 2）特点 03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ file:/F/temp/geektime/数据结构与算法之美/03复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？.html2019/1/15 15:35:11 以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响 ，所以在做时间复杂度分析时忽略这些项。 2.复杂度分析法则 1）单段代码看高频：比如循环。 2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。 3）
13、嵌套代码求乘积：比如递归、多重循环等 4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。 四、常用的复杂度级别？ 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括， O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n2)（平方阶）、O(n3)（立方阶） 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括， O(2n)（指数阶）、O(n!)（阶乘阶） 五、如何掌握好复杂度分析方法？ 复杂度分析关键在于多练，所谓孰能生巧。 389赞 作者回复
14、2018-09-26 00:43:35 总结的很棒 芳芳 2018-09-25 22:57:17 糟糕，是看不懂的感觉 132赞 Orcsir 2018-09-25 16:12:16 老师，代码片段把行号也写上吧。 61赞 作者回复2018-09-25 23:42:36 嗯嗯 我联系运营加上 吕宁 2018-09-26 01:56:01 老师好，我们上算法课，老师讲到存储一个二进制数，输入规模（空间复杂度）是O(logn) bit。请问如何理解？ 49赞 作者回复2018-09-26 05:08:27 比如8用二进制表示就是3个bit。16用二进制表示就是4个bit。以此类推 n用二进制表示就
15、是logn个bit halweg 2018-09-25 19:09:15 第二个例子中，第6.7行为什么是2n平方遍而不是n平方遍呢？ 34赞 作者回复2018-09-25 23:09:18 03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ file:/F/temp/geektime/数据结构与算法之美/03复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？.html2019/1/15 15:35:11 因为两层循环 一层是n 两层是n*n。不信你自己令n=5 自己算算 起名好难 2018-09-25 22:53:53 文章里也说了，性能测试这种是受环境所影响的。作为程
16、序员，我们能做的就是尽可能的降低复杂度，才能让代码在不同的环境下以最快的效率执行。至于 是不是浪费时间，我觉得其实是个伪命题。首先按刚刚分析过程来看，通过熟悉练习，简单的代码是可以直接看出来复杂度的也就是不费时间；而比较复杂 的代码就容易“一不小心”太“复杂”了，这个时候，为了代码质量考虑分析复杂度的时间也并不浪费。再有甚者，我们学习这个分析法，我觉得更多的是要明 白这个理念，在写代码的时候就能关注一下这方面的问题，毕竟复杂的代码在写的过程往往是先分析整体逻辑结构的，并且写的过程也需要不断思考，了解 这个理念后才能在写的过程中也思考关注这个点。不然，复杂的一段代码一旦写成，日后因为性能问题重构
17、，更费时间。 以上是对课后题的思考，欢迎批评指正。 另: 感觉加法法则那个图，maxf(n)+g(n) 换成max(f(n)+g(n)会不会更好些？ 30赞 作者回复2018-09-25 23:40:47 理解的非常透彻 非常有逻辑性 很赞。ps 图画错了 我联系运营改下 有一天 2018-09-26 09:02:39 一直有一个很纠结的问题，烦请解答一下：O具体是哪一个英文字母的缩写？ 28赞 作者回复2018-09-26 15:19:00 不是英文缩写 就是一个数学符号而已 realEago 2018-09-26 02:30:34 看不懂别慌，也别忙着总结，先读五遍文章先，无他，唯手熟尔 26赞 作者回复2018-09-26 04:59:07 说的太好了 我这里也没葵花宝典 学还是得靠自己 最爱小黑黑 2018-09-25 16:38:16 睡前刷一遍 明早起来再细看一遍 加油各位！ 23赞