时间戳

首页 > 解决方案 > 二分查找的时间复杂度不应该是O(ceil(logn))吗？

algorithm - 二分查找的时间复杂度不应该是O(ceil(logn))吗？

问题描述

这似乎是一个常见问题，可以在任何地方找到答案，但事实并非如此：我在 Internet 上的任何地方都找不到答案。关键是，我从来没有见过任何地方问过时间复杂度是否可能是O(ceil(logn))，我无法弄清楚，所以我决定在这里问一个问题。

首先，假设我有一个包含n数字的排序数组，并且我想使用二进制搜索算法在其中搜索一个值。下面列出了在最坏情况下所需的步骤数：

n 脚步
1 1
2 2
3 2
4 3
5 3
6 3
7 3
8 4
9 4
10 4

如您所见，n 个数字的数组所需的步骤是ceil(log2n)(ceil(log2n)表示大于或等于 的最小整数log2n)。所以我认为二分查找的时间复杂度应该是O(ceil(logn))，但是根据维基百科，时间复杂度应该是O(logn)，为什么？有什么不对？

标签： algorithmtime-complexitybig-obinary-search

解决方案

正如我已经在其他两个答案中解释的那样（参见此处和此处），Big-O 符号并不是大多数人认为的那样。它既不告诉你任何关于算法的速度，也不告诉你处理步骤的数量。

Big-O 唯一告诉您的是，如果输入元素的数量发生变化，算法的处理时间将如何变化。它保持不变吗？它是线性上升的吗？它是否以对数方式上升？它是二次上升的吗？这是 Big-O 唯一要回答的问题。

因此与两者O(5)相同，O(1000000)都只是简单地表示常数，通常写为O(1)。与通常写为 的简单均值线性O(n + 100000)相同。O(5n + 8)O(n)

我知道很多人会说“是的，但O(5n)比陡峭O(2n)”，这是绝对正确的，但它们仍然是线性的，Big-O 不是关于将两个具有线性复杂度的函数相互比较，而是关于将函数分类为粗略的类别。人们只是对这些类别以数学函数命名这一事实感到困惑，因此他们认为任何函数都可能适用于 Big-O 表示法，但事实并非如此。只有具有不同特征的函数才会有自己的 Big-O 符号。

以下概述远未完成，但在实践中主要是以下 Big-O 符号是相关的：

  • O(1)- 持续的
  • O(log log n)- 双对数
  • O(log n)- 对数
  • O((log n)^c), c > 1- 多对数
  • O(n^c), 0 < c < 1- 分数功率
  • O(n)- 线性
  • O(n log n) = O(log n!)- 线性的
  • O(n^2)- 二次
  • O(n^c), c > 1- 多项式
  • O(c^n), c > 1- 指数
  • O(n!)- 阶乘

除了把它们写成函数，也可以只给它们一个名字，但把它们写成函数有两个好处：有一些数学背景的人会立即在脑海中浮现出图形的图像，并且很容易引入新类型而无需只要你能用数学方式描述他们的图表，就可以想出花哨的名字。

推荐阅读