如何计算时间复杂度和空间复杂度

#algorithm

背景

我们在练习 LeetCode 算法题的时候，经常需要计算时间复杂度和空间复杂度。我们从简单的案例学习下如何计算时间复杂度和空间复杂度。

时间复杂度

计算原则：

  • 不要底阶项
  • 忽略高阶项的系数

举几个简单例子

  1. 无序数组排序

假设无序数组的长度为n

可以假设一个无序数组[6,5,1,3,4,2]用作试验

  • 从位置 0 遍历到位置 n - 1，取最小值放到位置 0，耗费时间 n
  • 从位置 1 遍历到位置 n - 1，取最小值放到位置 1，耗费时间 n - 1
  • 从位置 2 遍历到位置 n - 1，取最小值放到位置 2，耗费时间 n - 2
  • 如此循环到最后一个位置，耗费时间 1

如下面的遍历过程

位置         0    1   2   3   4 ...  (n - 3) (n - 2) (n - 1)
             ⊢-----------------------------------------⊣
遍历 n 次    min
                  ⊢------------------------------------⊣
遍历 n - 1 次     min
                      ⊢--------------------------------⊣
遍历 n - 2 次         min
                          ⊢----------------------------⊣
遍历 n - 3 次             min
.
.
.
                                                        ‖
遍历 1 次                                               min

最后把时间加起来

n + (n - 1) + (n -2) + ... + 1

根据等差数列求和公式

n * a1 + n * (n-1) / 2 * d

换算成

n * a1 + d / 2 * n ^ 2 - d / 2 * n

其中 a1、d / 2、d / 2都是常数系数，n用来计算

也可以把这个公式的常数简化下

a * n ^ 2 + b * n + c

根据时间复杂度的原则，不要低阶项 b * n 和 c，忽略高阶项a * n ^ 2 的系数 a，得到它的时间复杂度为 O(n ^ 2)

  1. 有序数组二分法找元素

假设一个有序数组[1,2,3,4,5,6,7,8]，寻找数字 7 所在位置

  • 第一次取得中间的位置 Math.floor((0 + 7) / 2) = 3，判断数字 4 < 7，继续找
  • 第二次取得中间的位置 Math.floor((3 + 7) / 2) = 5，判断数字 6 < 7，继续找
  • 第三次取得中间的位置 Math.floor((5 + 7) / 2) = 6，判断数字 7 == 7，找到位置 7
位置        1   2   3   4   5   6   7   8
第一次                  ▲
第二次                          ▲
第三次                              ▲

数组长度为 8,最多使用二分法找 3 次即可得到结果，我们发现log2(8) = 3，所以时间复杂度 O(log2(n)),通常简写为 O(log(n))

  1. 两个有序数组 A，B 求交集

A 数组长度 n，B 数组长度 m，因为无法比较 n 和 m 大小，也就无法确定哪个更高阶，所以时间复杂度都带上 n 和 m

有三种算法

  • 遍历所有 A，遍历所有 B，时间复杂度 O(n * m)
  • 遍历所有 A，二分遍历 B，时间复杂度 O(n * log(n))
  • 双指针遍历 A，B，时间复杂度 O(n + m)

空间复杂度

计算原则：

指额外空间，输入和输出用到的空间不计算在内

举一个简单例子，将一个有序数组逆序

  • 第一种方法：新建一个相同大小的辅助数组，倒着遍历这个数组，把所有内容插入到辅助数组，再把这个辅助数组返回，那么空间复杂度为 O(n)
  • 第二种方法：遍历这个数组，直接头尾两个指针的数字交换位置，没有新建辅助数组，而是直接在这个数组上操作，则空间复杂度为 O(1)

拓展学习

一个程序问题的算法最优解的含义：除特殊申明外，先满足时间复杂度最优情况下，使用最小空间。

总结

上面是小编最近在看一个入门算法视频课程所学习到的内容，简单的做一个编程学习笔记，更深入的算法复杂度计算，还有待进一步学习，后续小编学习到新的内容也会再更新，包括一些算法题解，leetcode刷题笔记，经典算法讲解等等。有问题的地方欢迎指出交流。

评论