V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Helsing
V2EX  ›  算法

请教一下这段代码的时间复杂度

  •  
  •   Helsing · 2020-12-02 11:01:51 +08:00 · 800 次点击
    这是一个创建于 370 天前的主题,其中的信息可能已经有所发展或是发生改变。
    // 全局变量,大小为 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;
    }
    

    这是我在一个课程里看到的例子,假如说调用 n 次 add 方法,最好时间复杂度最坏时间复杂度平均时间复杂度分别是多少?


    下面这个是课程评论中的一个答案,讲师也说是对的:

    1. 最好情况时间复杂度为 O(1)

    2. 最坏情况分析:

      最坏情况代码执行的次数跟每次数组的长度有关

      第 1 次调用 add 的执行的次数为 n ,

      第 2 次调用 add 的执行的次数为 2n ,

      第 3 次调用 add 的执行的次数为 2^2 * n

      第 k 次调用 add 的执行的次数为 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)

    5. 而均摊复杂度由于每次 O(len) 的出现都跟着 lenO(1),是前后连贯的,因而将 O(len) 平摊到前 len 次上,得出平摊复杂度是 O(1)


    但是按我的理解:

    • 最坏情况分析:

      最坏情况代码执行的次数跟每次数组的长度有关

      第 1 次调用 add 的执行的次数为 2^0 * 10,

      第 2 次调用 add 的执行的次数为 2^1 * 10 ,

      第 3 次调用 add 的执行的次数为 2^2 * 10

      第 n 次调用 add 的执行的次数为 2^(n-1) * 10 = 2^n * 5

      常系数可以省略,所以调用 n 次 add 方法的最差时间复杂度应该时 2^n

    我看课程评论里面都把数组的长度假设为 n,但是数组的初始长度明明是 10,这样假设的话跟上面的代码根本就不是一个意思了。我觉得 n 应该是调用 add 的次数才对。

    大家怎么看?

    目前尚无回复
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3814 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 01:41 · PVG 09:41 · LAX 17:41 · JFK 20:41
    ♥ Do have faith in what you're doing.