《数据结构与算法之美》入门篇笔记

2019-05-21

摘要：极客时间《数据结构与算法之美》入门篇笔记，时间复杂度和空间复杂度

主要内容

10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
10 个算法：递归、排序、二分查找、搜索、哈希算法、分治算法、回溯算法、动态规划、字符串匹配算法
algorithm

复杂度分析

大 O 时间复杂度

大 O 时间复杂度：又叫渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系，简称时间复杂度

function cal() {
  let sun = 0;
  let i = 1;
  for (; i <= n; i++) {
    sum += i;
  }
  return sum;
}

假设每段代码执行时间都一样为 unit_time，这段代码的总时间 T(n) = (2n+2)*umit_time
那么，下面的代码

function call() {
  let sum = 0;
  let i = 1;
  let j = 1;
  for (; i <= n; ++i) {
    j = 1;
    for (; j <=n; ++j) {
      sum += i * j;
    }
  }
}

总时间 T(n) = (2n^2+2n+3)*umit_time，由这两个总时间可以看出：所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比

大 O 复杂度表示法

1	T(n) = O(f(n))

T(n)表示代码执行的时间，n表示数据规模的大小，f(n)表示每行代码执行的次数总和，O表示代码的执行时间T(n)与f(n)表达式成正比。前两个例子时间复杂度可表示为：

1 2	T(n) = O(f(2n+2)) T(n) = O(f(2n^2+2n+3))

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势。当 n 很大时，公式中的低阶、常量、系数都可以忽略，因此可以记为：

1 2	T(n) = O(f(n)) T(n) = O(f(n^2))

时间复杂度分析

1、只关注循环执行次数最多的一段代码
2、加法法则：总复杂度等于量级最大的那段代码的复杂度
3、乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

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

1、多项式量级（递增）
常量阶 O(1)
对数阶 O(logn)
线性阶 O(n)
线性对数阶(nlogn)
平方阶 O(n^2)
立方阶 O(n^3)
k次方阶 O(n^k)

2、非多项式量级
增数阶 O(2^n)
阶乘阶 O(n!)
时间复杂度为非多项式量级的算法问题叫做 NP（Non-Deterministic Polynomial，非确定多项式）问题。当数据规模n越来越大是，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长，因此，非多项式时间复杂度的算法其实是非常低效的算法

多项式时间复杂度

1、O(1)
一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是O(1)

2、O(logn)/O(nlogn)
如下代码：

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

若 x 为执行次数：

1 2	2^x = n x = log2(n)

时间复杂度：

1	T(0) = O(log2(n))

根据换底公式，对数之间可以相互转换，只是系数不同。采用大 O 标记复杂度时可以忽略系数，因此在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为O(logn)
如果 O(logn) 执行了 n 遍，那么时间复杂度就是 O(nlogn) ，比如快速排序、归并排序

3、O(m+n)、O(m*n)
代码的复杂度由两个数据的规模来决定

function cal(m, n) {
  let sum_1 = 0;
  let i = 1;
  for (; i < m; ++i) {
    sum_1 += i;
  }
  let sum_2 = 0;
  let j = 1;
  for (; j < n; ++j) {
    sum_2 += j;
  }
  return sum_1 + sum_2;
}

无法评估 m 和 n 那个量级大，因此原来的加法法则需要变通：T1(m) + T2(n)= O(f(m) + g(n))
乘法法则不变：T1(m) * T2(n)= O(f(m) * g(n))
algorithm

空间复杂度分析

空间复杂度：全称渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系

function cal(n) {
  let i = 0;
  let a = new Array(n);
  for (i; i < n; ++i) {
    a[i] = i * i;
  }
  for (i = n-1; i >= 0; --i) {
    console.log(a[i]);
  }
}

第二行申请一个空间存储变量，但是他是常量阶的，跟数据规模 n 没有关系，忽略。第三行申请了一个长度为 n 的数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)

最好、最坏、平均、均摊时间复杂度

1、最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
2、最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度
3、平均情况时间复杂度：全称叫加权平均时间复杂度或者期望时间复杂度
分析下面代码：

function find(array, x) {
  let i = 0;
  let pos = -1;
  for (; i < array.length; ++i) {
    if (array[i] == x) {
      pos = i;
      break;
    }
  }
  return pos;
}

最好情况时间复杂度是 O(1) ，数组第一个元素就是要找的变量 x
最坏情况时间复杂度是 O(n) ，需要把整个数组都遍历一遍
平均情况时间复杂度是 O(n) ，假设在数组中与不在数组中的概率都为 1/2，那么执行的平均时间为

1	1 * i/(2n)+ 2 * 1/(2n) + 3 * 1/(2n) + ... + n * 1/(2n) + n * 1/2 = (3n + 1)/4

使用大 O 表示法来表示，去掉系数和常量后的加权平均时间复杂度为 O(n)

4、均摊时间复杂度：通过摊还分析得到的时间复杂度叫均摊时间复杂度，均摊时间复杂度就是一种特殊的平均时间复杂度，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。
分析下面代码：

// array 表示一个长度为 n 的数组
// 代码中的 array.length 就等于 n
let array = new Array(n);
let count = 0;
function insert(x) {
  if (count == array.length) {
    let sum = 0;
    for (int i = 0; i < array.length; ++i) {
      sum = sum + array[i];
    }
    array[0] = sum;
    count = 1;
  }
  array[count] = x;
  ++count;
}

这段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。
最好：插入时有位置 O(1)
最坏：需要遍历求和 O(n)
平均：

1	1 * 1/(1+n) + 1 * 1/(1+n) + 1 * 1/(1+n) + ... + 1 * 1/(1+n) + n * 1/(1+n) = (2n-1)/(1+n) => O(1)

均摊：每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)