数据结构与算法之美读后感_数据结构与算法之美读书报告

环境

MacBook Pro
极客时间

前言

均摊时间复杂度个人理解：

应用场景（自己的话）：

在对一个数据结构进行连续操作时，如果大部分情况都是O(1)，只有少部分情况是O(n)时，就可以使用均摊分析法。即将O(n)的情况，均摊到O(1)上。

课程原话：

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

举例来说：

// 全局变量，大小为10的数组array，长度len，下标i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个2倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来array数组中的数据依次copy到new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array复制给array，array现在大小就是2倍len了
     array = new_array;
     len = 2 * len;
   }
   // 将element放到下标为i的位置，下标i加一
   array[i] = element;
   ++i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

分析：

主要看循环次数最多的那个for循环;
上面的代码就是往数组里面插入元素

最好情况时间复杂度

O(1)， 即每次都不用走循环，都有位置插。

最坏情况时间复杂度

每次调这个方法时，都要走循环，即发生扩容：

第一次：n,
第二次：2n,
第三次：2^2 * n
第四次：2^3 * n
第k次：2^k * n

常量、系数和低阶可以省略。
所以复杂度为：O(n)

平均时间复杂度

因为插入数组的位置情况有n个，额外再加上扩容，共有n+1种情况，
所以每个位置的概率是：1/n+1，并且每种情况时间复杂度为O(1)，额外扩容的那种情况是O(n),所以加权平均数是：

p = 1/n+1
1* p + 1*p + 1*p ... ... + 1*p + n * p = O(1) 
// 这里没搞懂为啥是O(1)
1
2
3

为啥为O(1)呢???

只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。

上面表达式等于：

2n/(n+1) 
// 省略 常量
n/(n+1)
1
2
3

根据定义， 这个表达式，并不会因为n的增大，所以为O(1)复杂度。

均摊复杂度

个人理解：
当每次发生扩容后，后面又有经历多个O(1)的复杂度，也就是每次扩容后，紧接就是常量级的复杂度，那么可以把扩容那次O(n)的复杂度，均摊到每次的O(1)中去，这样最后均摊的复杂度就是O(1)。

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

参考地址：https://time.geekbang.org/column/article/40447
注意：该课程需要