美文网首页数据结构和算法分析极客时间:数据结构与算法之美笔记
复杂度分析(下)笔记:浅析最好、最坏、平均、均摊时间复杂度

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

作者: 红酥手黄藤酒丶 | 来源:发表于2018-12-21 21:56 被阅读3次

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

    最好时间复杂度和最坏时间复杂度在 渐近符号学习 中已经了解到了。

    一、平均时间复杂度

    // n 表示数组 array 的长度
    int find(int[] array, int n, int x) {
      int i = 0;
      int pos = -1;
      for (; i < n; ++i) {
        if (array[i] == x) {
           pos = I;
           break;
        }
      }
      return pos;
    }
    
    

    查找 x 在 数组中的位置,有 n + 1 中情况:在数组的 0~ n-1 位置不在数组中。把每种情况下,查找需要遍历的元素个数累加起来,除以 n-1 就可以得到需要遍历的元素个数的平均值(查找总数/可能情况 = 每种情况的查找次数):

    image

    求时间复杂度,忽略低阶项和常量因子后:平均时间复杂度为:○(n)


    image

    这个结论虽然是正确的,但是计算过程实际上出了一些问题,我们没有将事件发生的概率计算进去。

    什么概率呢?是变量 x 在数组中出现的概率和 出现位置的概率。出现在数组中和不出现在数组中的概率都为 ½ ,而出现在 0~n-1 这 n 个位置的概率为 1/n。所以根据概率乘法法则,x 出现在数组中任意位置的概率为 1/(2n)

    哎呦难受啊马飞,平均时间复杂度的计算过程又变了:

    image

    这个值就是概率论中的 加权平均值,也叫作 期望值。所以平均时间复杂度的全称应该叫做 加权平均时间复杂度 或者 期望时间复杂度

    但是可但是,根据近似原则,常量因子和低阶项还有什么系数之类的都去掉后,这段代码的加权平均时间复杂度仍然是 ○(n)。

    image

    二、均摊时间复杂度

    均摊时间复杂度对应的分析方法为 摊还分析(平摊分析)。均摊的应用场景比平均的应用场景更特殊,也就是说出现概率不高。

    //array 表示一个长度为 n 的数组
    //代码中的 array.length 就是 n
    int[] array = new int[n];
    int count = 0;
    
    void insert(int val){
        if(count == array.length){
            int sum = 0;
            for(int i = 0; i < array.length; ++i){
                sum = sum + array[I];
            }
            
            array[0] = sum;
            count = 1;
        }
        
        array[count] = val;
        ++count;
    
    }
    

    求上述代码的时间复杂度:
    成员变量 count 小于 n 时,每次执行 insert() 方法,都在向数组中添加数据,此时所用时间为常量时间,则为:○(1)。(最好)

    当成员变量 count 等于 n 时,执行循环语句,把数组中的数据累加到变量 sum 中,循环结束后将 sum 赋值给 数组下标为 0 的元素,将 count 重置为 1。此时所用时间为循环的遍历时间(取与n有关的时间,其他常量时间被忽略),则为:○(n)。(最坏)

    每次插入数据时,若 count 小于 n ,则复杂度为:○(1)(出现 n 次)。若 count 等于 n,则复杂度为:○(n)。这 n + 1 种情况出现的概率是相同的,根据 加权平均的计算方法

    image

    问题:那么 insert() 与 find() 有什么不同之处呢?
    不同之处在于 find() 只有在极端情况下(数组中无 x )复杂度才会为 ○(n),而 insert() 复杂度 ○(n) 出现的情况是有规律的:
    执行 n 次插入操作后,会执行 1 次遍历操作

    这种特殊的情况( 一个 ○(n)之后,紧接着就是 n - 1个 ○(1)),可以使用一种更加简单的分析方法:摊还分析法。对应的时间复杂度称为 均摊时间复杂度

    将执行循环的 ○(n) 均摊到每次执行插入的时间 ○(1),均摊下来,这一组连续的操作的均摊时间复杂度就为 ○(1)。

    解释一下:
    比如说,五个小朋友每个人吃1个苹果,然后一个大朋友自己吃五个苹果。均摊一下就是五个小朋友每个人吃两个。可以把对苹果的消耗理解为时间的消耗。所以一组满足特殊情况的操作的时间复杂度与n无关,是一个常量时间。

    image

    相关文章

      网友评论

        本文标题:复杂度分析(下)笔记:浅析最好、最坏、平均、均摊时间复杂度

        本文链接:https://www.haomeiwen.com/subject/pofjhqtx.html