01 复杂度分析

1 为什么要学习数据结构

 1. 我们要学习解决问题的方法，而不只是写代码
 2. 我们要关注程序的效率：时间和空间
 3. 数据结构和算法作为基础知识有助于学习更广泛或更深入的计算机知识

2 算法分析

 1. 需要衡量算法的效率，所以要有方法对算法进行时间和空间消耗的分析
 1. 由于实际测量的方式受环境和数据规模两方面的影响，所以不易于进行算法的衡量和分析
 1. 需要一个不用具体测量，可进行粗略估算的方法

3 算法复杂度

3.1 大O复杂度

 1. 算法在花费的时间T(n):与cpu执行次数成正比
 2. 执行次数:f(n) 与数据规模n有关
 3. T(n) = O(f(n)):O代表T(n)正比于O(f(n))

3.2 最好，最坏复杂度

3.3 均摊复杂度

某一类高数量级的操作不是每次都发生，它会随着某一个低复杂度的操作在某种情况下触发，将高数量级的操作分散到低复杂度操作触发高优先级操作的次数后
如：

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

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { 
        resize();
   }
   // 将element放到下标为i的位置，下标i加一
   array[i] = element;
   ++i;
}
void resize(){
// 重新申请一个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;
}

每n次插入会引发一次resize(),resize()会发生n+1次操作，加上操作n次赋值，add的操作次为:（2n+1)/n 所以T(n)=O(1)