数据结构（一）时间复杂度与空间复杂度

肆码难椎收录于数据结构与算法

2022-01-03 约 930 字预计阅读 2 分钟次阅读

开头

好记性不如烂笔头，在这里记录下学习数据结构与算法之美的笔记

简述

数据结构指的是‘一组数据的存储结构’，算法指的是’操作数据的一种方法‘。
数据结构是为算法服务的，算法要作用在特定的数据结构之上。

正片

复杂度分析

时间复杂度（大 O 复杂度表示法）

算法的执行效率，粗略的讲，就是算法代码的执行时间。

1
2
3
4
5
6
7
8


const (n) => {
  const sum = 0;
  const i = 1;
  for (; i <= n; ++i) {
    sum = sum + i;
  };
  return sum
}

假设每行代码执行的时间都一样，为 o,那么

第 2, 3 行分别需要一个 o 的执行时间；

第 4, 5 行都运行了 n 次，所以需要 2 个 n* o 的执行时间；

这段代码的总执行时间就是：（2n + 2）* o。

可以看出，每行代码的执行次数越多，总执行时间 T(n)就越高。按照这个思路，再看一段代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


const (n) => {
  const sum = 0;
  const i = 1;
  for (; i <= n; ++i) {
    const j = 1;
    for (; j <= n; ++j) {
      sum = sum + i + j;
    }
  };
  return sum
}

第 2、3、5 行需要一个 o 的执行时间；

第 4、5 行执行了 n 遍，需要 2 个 n * o 的执行时间；

第 7、8 行执行了 n^2 遍，需要 2 个 n^2 * o 的执行时间；

总执行时间为(2n^2 + 2n + 3) * o。

通过推导，得到一个公式T(n) = O(f(n)) t(n)表示代码的执行时间，f(n)表示代码执行次数的总和，所以，第一个例子中的 T(n) = O(2n + 2)和第二个例子的 T(n) = O(2n^2 + 2n + 3)。这就是大 O 时间复杂度表示法，他并不能具体表示代码的真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势。其中，f(n)中的低阶、常量、系数、三部分对增长趋势不产生绝对影响（在（2n^2 + 2n + 3）中，低阶是 2n、常量是 3、系数是 2），所以都可以省略，我们只需要记录一个最大量级就可以，因此，前两个例子的事件复杂度可以记为T(n) = O(n); T(n) = O(n^2)。

几种常见的时间复杂度

（按数量级排列）

常量阶： O(1)

1
2
3
4
5
6


// 只要代码的执行时间不随n的增大而增大，这样代码的时间复杂度都记作O(1)
const func = (n) => {
  const a = 1;
  const b = 2;
  return a + b;
};

对数阶： O(log n)

1
2
3
4


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

线性阶： O(n)
线性对数阶： O(n * log n)
平方阶： O(n^2)、立方阶： O（n^3）……
指数阶： O(2^n)
阶乘阶： O(n!)

空间复杂度

与时间复杂度同理，表示算法的存储空间与数据规模的增长关系。

常见的空间复杂度

O(1)、O(n)、o(n^2)

目录