英文:
Can big omega of log n be the average time complexity of a binary search?
问题
我知道二分查找的平均时间复杂度是 O(log n)。但由于大/坏情况和上下界概念是分开的，所以是否正确地说二分查找的平均时间复杂度也是 Ω(log n) 呢？最重要的是，如果是正确的，为什么是这样的呢？
英文:
I am aware that the average time complexity of a binary search is O(log n). But since the concept of big/worse case scenario and upper and lower bounds are separate, is it right to say that the average time complexity of a binary search is ALSO Ω(log n).
Most importantly, if it is right, why is that so?
答案1
得分: 3
Yes.
大O、Ω和Θ与最佳、最差和平均情况的时间复杂度概念无关。这是一个常见的误解。实际上，它们甚至不一定与时间复杂度相关。它们描述数学函数的渐近增长，你可以使用它们中的任何一个来描述算法的最佳、最差或平均时间复杂度。但你也可以用它们来描述与算法无关的某些函数。
至于二分查找，我们知道最坏和平均情况的时间复杂度都是对数的。因此，我们可以说这些复杂度都是Θ(log n)。然而，最佳情况的复杂度不是Θ(log n)，因为它是常数Θ(1)（在立即找到值时返回的实现中）。这是因为如果你恰巧在开始时找到了你要找的值，那么时间不取决于输入的长度。
然而，一个Θ(log n)的函数也是O(n)，实际上是O(n100)。这是根据大O符号的定义得出的。
因此，总结一下，以下陈述是正确的：
-
二分查找最坏情况时间复杂度和平均情况时间复杂度：Θ(log n)、O(log n)、O(n100)、Ω(log n)、Ω(1)。
-
二分查找最佳情况时间复杂度：Θ(1)、O(1)、O(log n)、O(n100)、Ω(1)。
但是，例如说平均情况时间复杂度是*O(1)或Ω(n)*都是错误的。
然而，请注意，如果我们说一个算法的时间复杂度是O(f(n))，那么通常我们会尽量用我们能找到的最紧密的界来表示它。因此，通常情况下，你不会告诉人们二分查找的时间复杂度是O(n)，即使从技术上来说它是正确的。然而，有些情况下，很容易证明是O(n)，但很难证明是O(log n)，那么即使*O(log n)也可能是正确的，说O(n)*也是完全正确的。
另请参阅这个不同但相似的问题及其早些时候发布的出色答案。
英文:
Yes.
Big-O, Ω and Θ are not related to the concepts of best, worse and average case time complexity. This is a common misconception. In fact, they are not even necessarily related to time complexity. They describe the asymptotic growth of mathematical functions, and you can use any of them to describe the best, worst or average time complexity of an algorithm. But you can also use them for some function that has nothing to with algorithms.
As for binary search, we know that both the worst and average case time complexity are logarithmic. So we can state that these complexities are both Θ(log n). The best-case complexity, however, is not Θ(log n) because it is constant, Θ(1) (in such implementations that return as soon as a value is found). This is because if you happen to find the value you were looking for at the very start, then the time does not depend on the length of the input.
However, a function that is Θ(log n) is also O(n) and indeed O(n<sup>100</sup>). This follows from the definition of big-O.
So in conclusion, the following statements are true:
-
Binary search worst-case time complexity and average time complexity: Θ(log n), O(log n), O(n<sup>100</sup>), Ω(log n), Ω(1).
-
Binary search best-case time complexity: Θ(1), O(1), O(log n), O(n<sup>100</sup>), Ω(1).
But e.g. saying that the average time complexity is O(1), or Ω(n), would be false.
Notice however, that if we say that an algorithm is O(f(n)), then we often try to express it with the tightest bound we can find. So you wouldn't normally go around telling people that binary search has O(n) time complexity - even if it is technically true. There are cases though where it is easy to prove O(n) but hard to prove O(log n), and then it is perfectly correct to say O(n) even if O(log n) might also be true.
Also see this different but rather similar question and its excellent answer posted earlier today.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论