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

四个复杂度分析:

1:最好情况时间复杂度(best case time complexity)

2:最坏情况时间复杂度(worst case time complexity)

3:平均情况时间复杂度(average case time complexity)

4:均摊时间复杂度(amortized time complexity)

for (; i < n; ++i)

{

if (array[i] == x)

{

pos = i;

break;

  }

  }

分析:1:最好情况时间复杂度:O(1)

2:最坏情况时间复杂度:O(n),因此在不同的情况下,这段代码的时间复杂度是不一样的,所以引入三个概念:最好,最坏,平均情况复杂度。

3:平均情况复杂度:

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

(1+2+3+……+n+n)/(n+1)=n(n+3)/2(n+1)

得到平均时间复杂度就是O(n)

  II:概率分析法

4:均摊时间复杂度(摊换分析,平摊分析)

上一篇:SpringBoot完美配置阿里云的文件上传


下一篇:基于hi-nginx的web开发(python篇)——表单处理和文件上传