全面分析算法复杂度

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了全面分析算法复杂度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1573字，纯文字阅读大概需要3分钟。

内容图文

在很多时候, 由于原始数据的不确定性, 算法的复杂度并不是唯一的, 可能具有多种不同的复杂度, 一个算法完整的时间复杂度分析包括如下:

• 最好情况时间复杂度（best case time complexity）;

• 最坏情况时间复杂度（worst case time complexity）;

• 平均情况时间复杂度（average case time complexity）;

• 均摊时间复杂度（amortized time complexity）;

show a code

// 在一个无序的数组（array）中，查找变量 x 出现的位置。如果没有找到，就返回 -1。
// 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 个数据了，那时间复杂度就是 O(1).

最坏情况时间复杂度

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

平均情况时间复杂度

最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实并不大。为了更好地表示平均情况下的复杂度，我们需要引入另一个概念：平均情况时间复杂度，后面我简称为平均时间复杂度.

• 简要分析(不考虑概率问题)

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

省略掉系数、低阶、常量，所以，咱们把刚刚这个公式简化之后，得到的平均时间复杂度就是 O(n).

• 更合理详细的分析

1. 假设在数组中与不在数组中的概率都为 1/2;
2. 且数据出现在 0～n-1 这 n 个位置的概率也是一样的, 为 1/n;

这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。用大 O 表示法来表示，去掉系数和常量，这段代码的加权平均时间复杂度仍然是 O(n)。

内容总结

以上是互联网集市为您收集整理的全面分析算法复杂度全部内容，希望文章能够帮你解决全面分析算法复杂度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---