Algorithm Challenge 02(Jul 12-13): asymptotic time complexity 2

复杂度相关的几个概念

最好情况时间复杂度（best case time complexity）

最坏情况时间复杂度（worst case time complexity）

平均情况时间复杂度（average case time complexity）

均摊时间复杂度（amortized case time complexity）

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

案例分析

// 全局变量，大小为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;
}

最好： O(1) 最坏： O(n) 最坏情况循环的次数与数组长度有关：第1次调用insert的执行的次数为 n , 第2次调用insert的执行的次数为 2n , 第3次调用insert的执行的次数为 2² n 第k次调用insert的执行的次数为 2^k-1 n 忽略常量所以还是O(n) 平均： O(1) 插入情况为n+1种： 0～n-1种O(1), 1次和插满之后可能调用的O(n), 2^k-1 n 次。每次插入概率为p = 1/(n+1) 加权平均时间复杂度：1 p+1 p+....+1 p+2^k-1 n p = O(1) 均摊： O(1) 每次O(n)之后都跟着n 次的O(1),前后连贯，所以把O(n)平摊到n次上，就是O(1)

666de6 / til