极客时间课程《数据结构与算法之美》01

复杂度计算

O (logn)

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

实际效果：

2^{0} *  2^{1} *  2^{2} ···  2^{k} ··· 2^{x}= n

通过 2x=n 求解 x 。
x=log2n，所以，这段代码的时间复杂度就是O (log2n)。

不管底数是几，所有对数阶的时间复杂度都记为
O (logn)。因为
O (log3n) = O(C * log2n)，使用大O标记复杂度的时候，可以忽略系数，所以同意表示为O (logn)。

比如，归并排序、快速排序的时间复杂度都是 O (nlogn)。

O(m+n)、O(m*n)

代码复杂度由两个数据的规模来决定。

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

其中m和n是表示两个数据规模，无法事先评估m和n哪个大，所以不能随意省略，故，上面代码的时间复杂度就是 O (m+n)。

空间复杂度

void print(int n) {
  int i = 0;
  int [ ] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

第2行申请一个空间存储变量i，可以忽略，和n无关。
第三行申请了大小为n的int类型数组，除此之外，无更多空间占用。故复杂度为O(n)。

均摊时间复杂度

大部分情况下，不必区分最好、最坏、平均情况时间复杂度三种情况。

 // array 表示一个长度为 n 的数组
 // 代码中的 array.length 就等于 n
 //这段代码仅仅是王争给的例子，没什么特殊实际意义。
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

我们还是继续看在数组中插入数据的这个例子。每一次 O (n) 的插入操作，都会跟着 n-1 次 O (1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O (1)。这就是均摊分析的大致思路。

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

均摊时间复杂度就是一种特殊的平均时间复杂度，没必要花太多精力去区分它们。最应该掌握的是它的分析方法，摊还分析。至于分析出来的结果是叫平均还是叫均摊，这只是个说法，并不重要。

新知

对于可反复读写的存储空间，认为它空即为空。清空数组有时候并不需要置为0，或某个值。把下标指到第一个位置就可以。

留言体会：平均和平摊基本就是一个概念，平摊是特殊的平均。在分析时间复杂度是 O (1) 还是 O (n) 的时候最简单就是凭感觉，，，，，，，，出现 O (1) 的次数远大于出现 O (n) 出现的次数，那么平均平摊时间复杂度就是 O (1)。。。。