复杂度分析与大O表示法

一言

在工程领域中，大量问题是难以达到最优解的，许多问题只是被”差不多“地解决了。问题的难易程度一方面取决于问题本身的性质，另一方面也取决于观测问题的人的知识储备。人的知识越完备，经验越多，分析问题就会越深入，问题就能被解决的更优雅。

如何进行算法效率的评估

如何分析、统计算法的执行效率和资源消耗

通常，在算法设计中，一般会先后追求以下两个层面的目标：解决问题和尽可能高效的解决问题，也就是说，我们的目标是设计”既快又省“的算法，那么如何有效的评估算法效率就显得尤为重要，业内主要有两种方式对算法进行评估，即：事后统计法和复杂度分析法。

• 事后统计法，又称实际测试法，一般采取的做法是把算法（代码）运行一遍，根据统计、监控就能得到算法执行的是时间和占用的内存大小。但这种做法有很大的局限性，主要在于，测试结果非常依赖于测试环境（如：运行机器的处理器性能），测试结果受到数据规模大小的影响很大如：对一组数据进行排序，有序的数据一定比无序数据执行效率高，再比如数据量太小的数据，测试结果也无法真实的反应算法的性能）。
• 复杂度分析法，又称大O复杂度表示法。此方法主要从时间复杂度和空间复杂度两个方面对算法进行理论上的估算，也是业内比较推荐的评估方法。

复杂度分析的定义

复杂度分析能够体现算法运行所需的时间和空间资源与输入数据大小之间的关系，它描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势。

针对事后统计法存在的局限性提出的解决方案, 不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方案，这种方案叫做复杂度分析法，也叫大O复杂度表示法。复杂度分析法分为：时间复杂度分析、空间复杂度分析

大O复杂度表示法

• 分类
  • 大O时间复杂度表示法（又称：渐进时间复杂度，简称：时间复杂度）
  • 大O空间复杂度表示法（又称：渐进空间复杂度，简称：空间复杂度）
• 公式：T(n)=O(f(n))
  • T(n) : 表示代码执行的时间，n表示数据规模的大小
  • fn: 表示每行代码执行次数的总和，这是一个公式，所以用fn表示
  • O: 表示代码执行时间T(n)与f(n)表达式成正比

如：T(n) = 2n * unit_time 、 T(n) = (2n2+2n+3)*unit_time。 fn: 2n / fn: (2n2+2n+3) T(n) = O(2n) / T(n) = O(2n2+2n+3)

• 总结：大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随着数据规模增长的变化趋势，故也称为渐进时间复杂度。

如何进行时间复杂度分析？

• 方法一：只关注循环执行次数最多的一段代码
  • 通常我们会忽略大O表示法公式中的常量、低阶、系统、只需要记录一个最大阶的量级就好，这段代码执行次数的n的量级，就是整段要分析代码的时间复杂度。
• 方法二：加法法则：总复杂度等于量级最大的那段代码的复杂度
  • 抽象成公式则为：如果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))*O(g(n))=O(f(n)*g(n)).

常见时间复杂度实例分析：

复杂度量级分类：

• 多项式量级：
  • 常量阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、k次方阶O(n^k)
• 非多项式量级：
  • 指数阶O(2n) 、 阶乘阶O(n!)
  • 当数据规模n越来越大是，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。

实例分析：

• 常量阶：O(1):
  • 常量级时间复杂度，并不是指只执行了一行代码；
  • 只要代码的执行时间不随n的增大而增大，这样的代码的时间复杂度就记作O(1)，
  • 只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，起时间复杂度依然是O(1)
• 对数阶：O(logn)、O(nlogn)
  • 所有对数阶的时间复杂度都是O(logn),不管是以2为底、还是以3为底、还是以10为底，因为对数之间就可以转换。
  • 如果一段代码的时间复杂度是O(logn), 当循环n编时，时间复杂度就是O(nlogn)
  • 在对数阶时间复杂度的表示方法里，尝尝忽略对数的底，统一表示为O(logn)
  • 时间复杂度为O(nlogn)的常见算法有：归并排序、快速排序
• O(m+n)、O(m*n)
  • 此类型的时间复杂度，由两个数据的规模来决定。

如何进行空间复杂度分析?

• 空间复杂度表示算法的存储空间和数据规模之间的增长关系
  • 常见的空间复杂度就是O(1)、O(n)、O(n2)
  • 不常见的空间复杂度有O(logn)、O(nlogn)，基本用不到

复杂度分析常见的概念

• 最好情况时间复杂度（best case time complexity）
  • 在最理想情况下，执行这段代码的时间复杂度
• 最坏情况时间复杂度（wrost case time complexity）
  • 在最糟糕情况下，执行这段代码的时间复杂度
• 平均情况时间复杂度（average case time complexity）
  • 简称：平均时间复杂度，由于最好和最坏都是在极端情况下的复杂度，发生的概率其实并不大，为了更好地表示平均情况下的复杂度，引入此概念。
• 均摊时间复杂度（amortized complexity）
  • 又称：摊还分析、平摊分析
  • 通过摊还分析法得到的时间复杂度
  • 均摊时间复杂度是一种特殊的平均时间复杂度

总结：

• 通常情况下，并不都是需要区分最好、最坏、平均情况时间复杂度的，使用一种复杂度就能满足需求了
• 只有同一块代码在不同的情况下，时间复杂度有量级的差距时，才会使用三种复杂度表示法来区分。