Back End

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

PineappleCat · 4月29日 · 2021年 82次已读
  • 最好情况时间复杂度(best case time complexity)
  • 最坏情况时间复杂度(worst case time complexity)
  • 平均情况时间复杂度(average case time complexity)
  • 均摊时间复杂度(amortized time complexity)

最好、最坏情况时间复杂度

引入概念举例:

循环数组查找与x相等的元素,并不一定需要把数组循环一边。

可能的情况:

  • 第一个元素与相等,时间复杂度为O(1)
  • 没有元素与x相等,时间复杂度为O(n)

为了表示代码在不同情况下的不同时间复杂度:最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度

  • 最好情况时间复杂度:在最理想的情况下,执行这段代码的时间复杂度
  • 最坏情况时间复杂度:在最糟糕的情况下,执行这段代码的时间复杂度

平均情况时间复杂度

概念的引入:最好与最坏时间复杂度出现的概率是低的,为了更好的表示算法的时间复杂度引入了平均时间复杂度的概念。

平均时间复杂度又该怎么分析呢?

同上数组中查找相等元素:要查找的变量x在数组中的位置有n+1种情况:在数组的0~n-1位置中和不在数组中。我们把每种情况下,查找需要遍历的元素个数累加起来,然后再除以n+1,
就可以得到需要遍历的元素个数的平均值,即:

省略掉系数、低阶、常量,得到的平均时间复杂度就是O(n)

加权平均时间复杂度或者期望时间复杂度

上面我们直接相加却没有考虑每个情况的概率问题。

假设在数组中与不在数组中的概率都为1/2。另外,要查找的数据出现在0~n-1这n个位置的概率也是一样的,为1/n。所以,根据概率乘法法则,要查找的数据出现在0~n-1中任意位置的概率就是1/(2n)。

加权平均时间复杂度仍然是O(n)。

均摊时间复杂度

均摊时间复杂度,以及它对应的分析方法,摊还分析(或者叫平摊分析)

大部分情况下,我们并不需要区分最好、最坏、平均三种复杂度。平均复杂度只在某些特殊情况下才会用到,而均摊时间复杂度应用的场景比它更加特殊、更加有限。

对这段代码的解释:开始不断往数组中添加元素,当count==数组长度时,将数组中元素进行加和放到下标为0的位置,count指向1,相当于清空了数组。

这段代码与之前数组中找相等的元素代码不同点为:

  • insert()在大部分情况下,时间复杂度都为O(1)。只有个别情况下,复杂度才比较高,为O(n)
  • insert()函数来说,O(1)时间复杂度的插入和O(n)时间复杂度的插入,出现的频率是非常有规律的

针对这种特殊的场景,我们引入了一种更加简单的分析方法:摊还分析法,通过摊还分析得到的时间复杂度我们起了一个名字,叫均摊时间复杂度。

继续看在数组中插入数据的这个例子。每一次O(n)的插入操作,都会跟着n-1次O(1)的插入操作,所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上,均摊下来,这一组连续的操作的均摊时间复杂度就是O(1)。

对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系,这个时候,我们就可以将这一组操作放在一块儿分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。而且,在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度。


Click here to view the copyright notice of this site(点击此处查看本站版权声明)
0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!