algorithm - 算法的 theta 界是唯一的吗？

Question

例如，二分搜索的最严格界限是θ(logn)，但我们也可以说它有O(n^2)和Ω(1)。

但是，我很困惑我们是否可以说像"Binary search has a θ(n) bound"since θ(n) is between O(n^2)and Ω(1)?

标签： algorithmbig-ocomplexity-theory

Answer 1

• 对大小为n的数组执行二分查找的最坏情况使用Θ(log n)操作。
• 在大小为n的数组上执行任何二进制搜索都使用O(log n)操作。
• 在大小为n的数组上执行二进制搜索的一些“幸运”执行使用O(1)操作。

“二分搜索的复杂性有一个Θ(n)界限”这句话是如此模棱两可且具有误导性，以至于大多数人会称之为错误。一般来说，我建议您不要在同一个句子中使用“绑定”一词作为符号O( )、Θ( )、Ω( )之一。

• log n < n是真的。
• log n = Θ(n)是错误的。
• 语句log n < Θ(n)在技术上是正确的，但具有误导性，因此您永远不应该编写它。
• 确实log n = O(n)。