复习下数列知识

大 O 阶推导方法 - 图1

大 O 阶推导方法 - 图2

大 O 阶推导方法 - 图3

等比数列：
大 O 阶推导方法 - 图4

大 O 阶推导方法 - 图5

大 O 阶推导方法

  1. 用常数 1 取代运行时间中的所有加法常数
  2. 在修改后的运行次数函数中，只保留最高阶项
  3. 如果最高阶项存在且不是 1，则去除与这个项相乘的常数

    常数阶

    1. sum, n := 0, 100        /* 执行一次 */
    2. sum = (1 + n) * n / 2    /* 执行一次 */
    3. fmt.Println(sum)        /* 执行一次 */
    这个算法的运行次数函数是 f(n) = 3，根据大 O 阶推导方法，第一步就是把常数项 3 改为 1，发现根本没有最高阶项，因此该算法时间复杂度为 O(1)

    线性阶

    1. for i := 0; i < n; i++ {
    2.  /* 时间复杂度为 O(1) 的程序步骤序列 */
    3. }
    这段代码的时间复杂度为 O(n)，因为循环体中的代码执行了 n 次

    对数阶

    1. count := 1
    2. for count < n {
    3.  count = count * 2
    4.  /* 时间复杂度为 O(1) 的程序步骤序列 */
    5. }
    由于每次 count 乘以 2 之后，就距离 n 更近了一分，即，有多少个 2 相乘后大于 n 使得代码退出循环，算法时间复杂度就为多少。由 2x = n 得 x = log2n，所以时间复杂度为 O(log2n) ，如果 count = count * 2 改为 count = count * 3，时间复杂度则为 O(log3n)

但实际上，底数不是很重要，一般直接说对数阶 O(log n)

平方阶

  1. for i := 0; i < n; i++ {
  2.     for j := 0; j < n; j++ {
  3.         /* 时间复杂度为 O(1) 的程序步骤序列 */
  4.     }
  5. }

外层循环每一次都会执行 n 次内层循环，所以时间复杂度为 O(n * n)，即 O(n2)

如果改变某一层的执行次数，如：

  1. for i := 0; i < m; i++ {
  2.     for j := 0; j < n; j++ {
  3.         /* 时间复杂度为 O(1) 的程序步骤序列 */
  4.     }
  5. }

时间复杂度就变为 O(m * n)

因此可以总结得出，循环的时间复杂度等于循环体的复杂度乘以该循环执行的次数

但是对于以下的情况：

  1. for i := 0; i < n; i++ {
  2.     for j := i; j < n; j++ {
  3.         /* 时间复杂度为 O(1) 的程序步骤序列 */
  4.     }
  5. }

由于当 i = 0 时，内循环执行了 n 次，当 i = 1 时，内循环执行了 n - 1 次，……，当 i = n - 1 时，内循环执行了 1 次，所以总的执行次数为：
大 O 阶推导方法 - 图6

再使用大 O 阶推导方法：
首先，没有加法常数不考虑，
其次，只保留最高次项，因此保留 ，
最后，去除这个项的常数系数 ，最终时间复杂度为 O(n2)

可见理解大 O 阶推导并不难，难的是对数列的一些相关运算，因此数学功底尤其是数列相关的知识要扎实

下面看对于函数（或方法）调用的时间复杂度如何分析：

  1. func main() {
  2.     for i := 0; i < n; i++ {
  3.         hello(i);
  4.     }
  5. }
  7. func hello(count int) {
  8.     fmt.Println(count)
  9. }

函数体是打印这个参数，因为只打印一次所以时间复杂度为 O(1)，整体的时间复杂度为 O(n * 1) 即 O(n)

改一下：

  1. func main() {
  2.     for i := 0; i < n; i++ {
  3.         hello(i);
  4.     }
  5. }
  7. func hello(count int) {
  8.     for j := count; j < n; j++ {
  9.         /* 时间复杂度为 O(1) 的程序步骤序列 */
  10.     }
  11. }

和上上个例子同理，因此整体的时间复杂度为 O(n2)

再看一个复杂的例子：

  1. func main() {
  2.     n++                                /* 执行次数为 1 */
  3.     hello(n)                        /* 执行次数为 n */
  4.     for i := 0; i < n; i++ {        /* 执行次数为 n^2 */
  5.         hello(i);
  6.     }
  7.     for i := 0; i < n; i++ {        /* 执行次数为 n(n+1)/2 */
  8.         for j := i; j < n; j++ {
  9.             /* 时间复杂度为 O(1) 的程序步骤序列 */
  10.         }
  11.     }
  12. }
  14. func hello(count int) {
  15.     /* 时间复杂度为 O(1) 的程序步骤序列 */
  16. }

执行次数为：

根据大 O 阶推导方法，这段代码的时间复杂度也为 O(n2)

常见的时间复杂度

image.png
上述排序中，从左到右，对应的数学阶数越来越大

平方阶以上就算是不切实际的算法了

最坏情况与平均情况

一般在无特殊说明的情况下，都是指最坏时间复杂度

算法空间复杂度

算法空间复杂度的计算公式为：S(n) = O(f(n))，其中，n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数

若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为 O(1)