赞
踩
MacBook Pro
极客时间
均摊时间复杂度个人理解:
应用场景(自己的话):
在对一个数据结构进行连续操作时,如果大部分情况都是O(1),只有少部分情况是O(n)时,就可以使用均摊分析法。即将O(n)的情况,均摊到O(1)上。
课程原话:
对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系,这个时候,我们就可以将这一组操作放在一块儿分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。而且,在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度。
举例来说:
// 全局变量,大小为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; }
分析:
主要看循环次数最多的那个
for
循环;
上面的代码就是往数组里面插入元素
O(1)
, 即每次都不用走循环,都有位置插。
每次调这个方法时,都要走循环,即发生扩容:
第一次:n,
第二次:2n,
第三次:2^2 * n
第四次:2^3 * n
第k次:2^k * n
常量、系数和低阶可以省略。
所以复杂度为:O(n)
因为插入数组的位置情况有n个,额外再加上扩容,共有n+1
种情况,
所以每个位置的概率是:1/n+1
,并且每种情况时间复杂度为O(1)
,额外扩容的那种情况是O(n)
,所以加权平均数是:
p = 1/n+1
1* p + 1*p + 1*p ... ... + 1*p + n * p = O(1)
// 这里没搞懂为啥是O(1)
为啥为O(1)
呢???
只要代码的执行时间不随 n 的增大而增长,这样代码的时间复杂度我们都记作 O(1)。
上面表达式等于:
2n/(n+1)
// 省略 常量
n/(n+1)
根据定义, 这个表达式,并不会因为n的增大,所以为O(1)复杂度。
个人理解:
当每次发生扩容后,后面又有经历多个O(1)的复杂度,也就是每次扩容后,紧接就是常量级的复杂度,那么可以把扩容那次O(n)的复杂度,均摊到每次的O(1)中去,这样最后均摊的复杂度就是O(1)。
课程的解释:
每一次 O(n) 的插入操作,都会跟着 n-1 次 O(1) 的插入操作,所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上,均摊下来,这一组连续的操作的均摊时间复杂度就是 O(1)
参考地址:https://time.geekbang.org/column/article/40447
注意:该课程需要
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。