数据结构与算法之美04

数据结构与算法之美04

复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度

一、复杂度分析的4个概念
1.最坏情况时间复杂度:代码在最理想情况下执行的时间复杂度。
2.最好情况时间复杂度:代码在最坏情况下执行的时间复杂度。
3.平均时间复杂度:用代码在所有情况下执行的次数的加权平均值表示。
4.均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

二、为什么要引入这4个概念?
1.同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码的时间复杂度,所以引入这4个概念。
2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下,是不需要区别分析它们的。

三、如何分析平均、均摊时间复杂度?
1.平均时间复杂度
代码在不同情况下复杂度出现量级差别,则用代码所有可能情况下执行次数的加权平均值表示。
2.均摊时间复杂度
两个条件满足时使用:1)代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度;2)低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

// 全局变量,大小为 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), 均摊是O(1)。

看到好多人纠结于清空数组的问题: 对于可反复读写的存储空间,使用者认为它是空的它就是空的。如果你定义清空是全部重写为0或者某个值,那也可以!但是老师举的例子完全没必要啊!写某个值和写任意值在这里有区别吗,使用值只关心要存的新值!所以老师的例子,清空把下标指到第一个位置就可以了!

看了大家的留言总结的很好,自己把练习题的答案整理了一下与大家分享:
1. 最好情况时间复杂度为 O(1)
2.最坏情况分析: 
最坏情况代码执行的次数跟每次数组的长度有关
第1次调用insert的执行的次数为 n ,
第2次调用insert的执行的次数为 2n ,
第3次调用insert的执行的次数为 2^2 * n 
第k次调用insert的执行的次数为 2^(k-1) * n 
最坏时间复杂度为 O(n)。
3. 平均情况分析
当每次遇到最坏情况时数组会进行2倍扩容,原数组被导入新数组,虽然数组的长度变大了,但是插入操作落在的区间的长度是一样的,分别是0~len-1, len~(2len-1),….;
插入的情况仍是len+1种:0~len-1和插满之后的O(len);所以每次插入的概率是:p= 1/len+1,
最后求出加权平均时间复杂度为 1*p + 2*p+ ▪▪▪ + len*p + len * p = O(1) ; 
4. 均摊时间复杂度 O(1)
而均摊复杂度由于每次O(len)的出现都跟着len次O(1),是前后连贯的,因而将O(len)平摊到前len次上,得出平摊复杂度是O(1)

发表评论

电子邮件地址不会被公开。 必填项已用*标注