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

精选留言(1117)

• 

  xr

  我不认为是多此一举，渐进时间，空间复杂度分析为我们提供了一个很好的理论分析的方向，并且它是宿主平台无关的，能够让我们对我们的程序或算法有一个大致的认识，让我们知道，比如在最坏的情况下程序的执行效率如何，同时也为我们交流提供了一个不错的桥梁，我们可以说，算法1的时间复杂度是O(n)，算法2的时间复杂度是O(logN)，这样我们立刻就对不同的算法有了一个“效率”上的感性认识。
  
  当然，渐进式时间，空间复杂度分析只是一个理论模型，只能提供给粗略的估计分析，我们不能直接断定就觉得O(logN)的算法一定优于O(n), 针对不同的宿主环境，不同的数据集，不同的数据量的大小，在实际应用上面可能真正的性能会不同，个人觉得，针对不同的实际情况，进而进行一定的性能基准测试是很有必要的，比如在统一一批手机上(同样的硬件，系统等等)进行横向基准测试，进而选择适合特定应用场景下的最有算法。
  
  综上所述，渐进式时间，空间复杂度分析与性能基准测试并不冲突，而是相辅相成的，但是一个低阶的时间复杂度程序有极大的可能性会优于一个高阶的时间复杂度程序，所以在实际编程中，时刻关心理论时间，空间度模型是有助于产出效率高的程序的，同时，因为渐进式时间，空间复杂度分析只是提供一个粗略的分析模型，因此也不会浪费太多时间，重点在于在编程时，要具有这种复杂度分析的思维。

  作者回复: 写得很好。理解的到位
  

  2018-09-26

   14

   1128
• 

  姜威

  总结
  一、什么是复杂度分析？
  1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
  2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
  3.分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
  4.复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。
  二、为什么要进行复杂度分析？
  1.和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
  2.掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。
  三、如何进行复杂度分析？
  1.大O表示法
  1）来源
  算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。
  2）特点
  以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽略这些项。
  2.复杂度分析法则
  1）单段代码看高频：比如循环。
  2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
  3）嵌套代码求乘积：比如递归、多重循环等
  4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。
  四、常用的复杂度级别？
  多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，
  O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶）
  非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，
  O(2^n)（指数阶）、O(n!)（阶乘阶）
  五、如何掌握好复杂度分析方法？
  复杂度分析关键在于多练，所谓孰能生巧。

  作者回复: 总结的很棒

  2018-09-26

   12

   730
• 

  芳芳

  糟糕，是看不懂的感觉

  2018-09-26

   1

   242
• 

  吕宁

  老师好，我们上算法课，老师讲到存储一个二进制数，输入规模（空间复杂度）是O(logn) bit。请问如何理解？

  作者回复: 比如8用二进制表示就是3个bit。16用二进制表示就是4个bit。以此类推 n用二进制表示就是logn个bit

  2018-09-26

   10

   161
• 

  Orcsir

  老师，代码片段把行号也写上吧。

  作者回复: 嗯嗯 我联系运营加上

  2018-09-26

  

   75
• 

  realEago

  看不懂别慌，也别忙着总结，先读五遍文章先，无他，唯手熟尔~

  作者回复: 说的太好了 我这里也没葵花宝典 学还是得靠自己

  2018-09-26

   2

   67
• 

  起名好难

  文章里也说了，性能测试这种是受环境所影响的。作为程序员，我们能做的就是尽可能的降低复杂度，才能让代码在不同的环境下以最快的效率执行。至于是不是浪费时间，我觉得其实是个伪命题。首先按刚刚分析过程来看，通过熟悉练习，简单的代码是可以直接看出来复杂度的也就是不费时间；而比较复杂的代码就容易“一不小心”太“复杂”了，这个时候，为了代码质量考虑分析复杂度的时间也并不浪费。再有甚者，我们学习这个分析法，我觉得更多的是要明白这个理念，在写代码的时候就能关注一下这方面的问题，毕竟复杂的代码在写的过程往往是先分析整体逻辑结构的，并且写的过程也需要不断思考，了解这个理念后才能在写的过程中也思考关注这个点。不然，复杂的一段代码一旦写成，日后因为性能问题重构，更费时间。
  
  以上是对课后题的思考，欢迎批评指正☺。
  另: 感觉加法法则那个图，maxf(n)+g(n) 换成max(f(n)+g(n))会不会更好些？

  作者回复: 理解的非常透彻 非常有逻辑性 很赞。ps 图画错了 我联系运营改下

  2018-09-26

  

   52
• 

  halweg

  第二个例子中，第6.7行为什么是2n平方遍而不是n平方遍呢？

  作者回复: 因为两层循环 一层是n 两层是n*n。不信你自己令n=5 自己算算

  2018-09-26

   5

   41
• 

  有一天

  一直有一个很纠结的问题，烦请解答一下：O具体是哪一个英文字母的缩写？

  作者回复: 不是英文缩写 就是一个数学符号而已

  2018-09-26

   2

   38
• 

  最爱小黑黑

  睡前刷一遍 明早起来再细看一遍 加油各位！

  2018-09-26

   1

   38
• 

  scarlett

  回答 thinkings 的问题
  i=1;
  while (i <= n) {
  i = i * 2
  }
  假设n= 20，i每次的取值是2 4 8 16 执行4次，时间复杂度是O(log2n)
  i=1;
  while (i <= n) {
  i = i + 2
  }
  假设 n=20 i每次取值：3，5，7，9，11，13，15，17，19 ，执行9次，时间复杂度是O(n/2),根据老师讲的 公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略，所以是O（n）

  作者回复: 👍 分析的通俗易懂 棒棒哒

  2018-09-26

   4

   37
• 

  dickwxyz@126.com

  没有看懂，所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2x=n 求解 x 这个问题我们想高中应该就学过了，我就不多说了。 这里的x不就是代码里的n吗，时间复杂度不是O(n)吗？

  作者回复: i 第一次等于1
  第2次等于2
  第3次等于2*2
  第4次等于2*2*2
  .....
  第x次等于2的x-1次方
  ……
  那第几次之后等于n呢
  
  也就是2的x-1次方等于n求解x
  
  x粗略点讲就近似于logn
  
  也就是代码执行了logn遍就退出循环了
  
  所以根据大o标记法 为logn
  
  
  
  

  2018-09-26

   4

   30
• 

  Monday

  本节通读两遍，通俗易懂，对复杂度的概念有了新的认识。
  复杂度就是用来分析算法执行效率与数据规模之间增长关系。
  思考题，性能测试与复杂度分析不冲突，原因如下：
  1、性能测试是依附于具体的环境，如SIT、UAT机器配置及实例数量不一致结果也有差别。
  2、复杂度分析是独立于环境的，可以大致估算出程序所执行的效率。
  3、将复杂度熟记于心，能够写出更高效率、更好性能的代码。若某接口通过性能测试，达不到预期，还可以用复杂度分析接口代码，找出最影响性能的代码，进行优化。
  
  每段代码都分析一下时间复杂度、空间复杂度，是不是很浪费时间呢？
  这个问题分两种情况讨论
  1、开发过程中，码代码的过程中就能得出其复杂度，这并不会太多的浪费时间，同时只有分析了每段代码的复杂度，才能估算出它们的执行效率。
  2、优化代码时，只有在分析每段代码的复杂度后，才能定位问题代码，才能做相应优化
  
  另外提出两个问题：
  1、评论太多，也无法进行关键字搜索，一般没有时间爬楼全部看完，导致不同学友提出一样的问题
  2、评论太多，可能有些评论不正确，需要官方确认正确与否，以免误导学友。
  
  
  

  作者回复: 理解的很透彻！

  2018-09-26

   1

   26
• 

  冯剑

  在分析多项式复杂度的时候，有根据输入规模确定复杂度O(m+n),我的理解是 假设n是相对比较大的值，那么这个复杂度O(m+n)<=O(2n)，2是常量，这样的话复杂度不就是O(n),请问下，O(n)和O(m+n)的区别在什么地方？有什么应用场景能体现出二者不同

  2018-09-26

   3

   26
• 

  陈华应

  有必要，基准测试是事后，也是理论验证，有时候O(n)未必一定比O(1)效率低。
         复杂度分析是理论，整体趋势上反应了一个算法的时间或者空间利用率与数据规模的渐进关系，并且像程序员之间使用设计模式来讨论代码设计一样，说出名字就大致知道代码是如何组织的，大O也是一样。
          随着自己使用大O分析代码复杂度的熟练程度增加，判断一段代码的复杂度可能分分钟的事情，甚至更快。
  

  作者回复: 理解的很透彻！

  2018-09-26

  

   18
• 

  Dwyane

  03
  大家好，这是我的总结：
  
  公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略
  1. 只关注循环执行次数最多的一段代码
  2.加法法则：总复杂度等于量级最大的那段代码的复杂度
  3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
  
  
  只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们集作O(1)
  不同数据规模，无法评估 m 和 n 的量级大，所以不能利用加法法则，去掉某一个，而是 O(m+n)
  
  空间复杂度：表示算法的存储空间与数据规模之间的增加关系
  
  额外说一下：log3n 就等于 log32 * log2n 其实是利用换底公示推导，有疑问的搜一下。

  作者回复: 是换底公式 👍

  2018-09-26

  

   17
• 

  短迪大魔王

  很有必要，现在是大数据时代，如果是矩阵计算，那就是on，如果是传统双for遍历那就是on²，做lr不依托矩阵都要天荒地老，那神经网络尤其是rnn就不用做了，即使是84万文本数据，长度为20个词，用单机gpu加速要跑七天。双for是几天那？经典例子是马踏棋盘，没优化代码跑几天，优化了又看不懂，问问老师如何对代码做优化，因为优化了就读不懂了有没有？
  空间复杂度也有必要，还是nlp的例子，如果是embending的话，内存开销和磁盘开销都小的多，虽然现在分布式允许无限大，但是生产环境要把数据传到hdfs，再传到训练集群上，这都有网络传输开销啊，其二是可能没有这个权限，不安全。其三，生成npy文件不能shuffle，很不便利，也不允许分割，所以事先要想好空间要怎么来。当然时间更重要，敏捷迭代。

  2018-09-26

  

   15
• 

  ChaoYrAx

  老师 空间复杂度 和时间复杂度的 具体区别是什么，我怎么看上去像一样的

  作者回复: 一个表示内存的消耗 一个表示执行的快慢

  2018-09-26

  

   15
• 

  

  考研数据结构会考到🤓🤓

  2018-09-26

  

   14
• 

  huangjh

  有必要，性能测试更多的是一种实验结果。而复杂度分析，可以帮助我们分析内因。

  作者回复: 简洁到位！

  2018-09-27

  

   13