数据结构与算法-03-复杂度分析(上)-如何分析、统计算法的执行效率和资源消耗?

发表于 | 评论数：

本小结主要讲解了时间复杂度和空间复杂度。主要解释了如下几个问题

  • 为什么需要复杂度分析？
  • 大O复杂度表示法
  • 时间复杂度分析的方法
  • 空间复杂度的分析方法

为什么需要复杂度分析？

Q：直接把程序拿到环境中跑一下不就可以了吗？
A：不可以，因为每个机器的环境不同，数据不同，无法对比。虽然这种方法竟然也被称为 事后统计法

大O复杂度表示法

注意：大O时间复杂度表示法 实际上并具体表示代码的真正执行时间，而是表示代码执行时间随数据的规模增长的变化趋势，所以，也叫作 渐进时间复杂度，简称为复杂度

时间复杂度分析的方法

  • 只关注循环中次数最多的一段代码
  • 加法法则：总复杂度等于量级最大的那段代码的复杂度
    如果 T1(n)=O(f(n))，T2(n)=O(g(n))那么 T(n)=T1(n)+T2(n)=max(O(f(n), O(g(n))) =O(max(f(n), g(n)))
  • 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
    如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)*T2(n)=O(f(n)*g(n)).

几种常见时间复杂度实例分析

几种常见的复杂度

注意，看如下代码,我们能够很容易的知道，这个时间复杂度是O(log2 n) = O(log n)

1
2
3
4
i=1;
while (i <= n)  {
  i = i * 2;
}

再看如下代码，我们也能够很容易的知道其复杂度为O(log3 n)，有因为O(log3 n) = O(log3 2) * O(log2 n),
因为分析时间复杂度的时候，会忽略常量系数，所以最终的时间复杂度还是O(log n)

1
2
3
4
i=1;
while (i <= n)  {
  i = i * 3;
}

空间复杂度分析

空间复杂度分析就是看其所占用的空间与数据规模n的关系，我们常见的空间复杂度就是O(1)、O(n)、O(n2)，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。

总结

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )

常见的复杂度图像

课后思考

有人说，我们项目之前都会进行性能测试，再做代码的时间复杂度、空间复杂度分析，是不是多此一举呢？而且，每段代码都分析一下时间复杂度、空间复杂度，是不是很浪费时间呢？你怎么看待这个问题呢？

个人认为：项目之间会评估整个项目的架构是否合理，性能预估是否达标，但是并不代表项目做出来之后性能就是好的，当在写项目代码的时候，如果能够把时间复杂度和空间复杂度这两个概念贯穿整个编程的脑海中，那么第一能够锻炼自己的思维，第二也能够写出高质量的代码，能够提升性能，毕竟对一个公司来说，性能提升可能就意味着利润的上涨。