首页 > 其他 > 详细

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

时间:2020-02-15 20:21:20      阅读:67      评论:0      收藏:0      [点我收藏+]

最好情况时间复杂度(best case time complexity)、最坏情况时间复杂度(worst case time complexity)、平均情况时间复杂度(average case time complexity)、均摊时间复杂度(amortized time complexity)。如果这几个概念你都能掌握,那对你来说,复杂度分析这部分内容就没什么大问题了。

// 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 可能出现在数组的任意位置。

如果数组中第一个元素正好是要查找的变量 x,那就不需要继续遍历剩下的 n-1 个数据了,那时间复杂度就是 O(1)。

但如果数组中不存在变量 x,那我们就需要把整个数组都遍历一遍,时间复杂度就成了 O(n)。

所以,不同的情况下,这段代码的时间复杂度是不一样的。

技术分享图片

 

 技术分享图片

 

 

 

 

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

原文:https://www.cnblogs.com/lakeslove/p/12313266.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!