day02 四种时间复杂度分析方法

一、时间复杂度有哪几种？

• 最好时间复杂度
• 最坏时间复杂度
• 平均时间复杂度（概率）
• 均摊时间复杂度（特殊的平均时间复杂度；将较高复杂度那次操作耗时，平摊到其他那些时间复杂度比较低的操作上）

二、练习题：时间复杂度分析 add 函数

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

当数组的内元素小于10的时候，可以直接插入，此时时间复杂度为O（1）

最坏时间复杂度为：O(n)

当插入的数据位置为n+ 1, 切n > 10 的时候，需要重新申请数组空间，原数组内copy到新的数组内。当n比较大时，需要拷贝 n 次。此时的时间复杂度为O（n）

均摊时间复杂度： O()

每一次O（n）的添加操作，都伴随着n-1次的O（1）操作。此时将耗时的O（n）操作均摊到n-1次操作上，此时的时间复杂度为：O（1） + O（1） +..... + O（1） = O（1）