time-complexity - 二分搜索算法时间复杂度

Question

我在 Cormen 书中研究的二元 Saerch 算法的时间复杂度是：

• 最佳案例 - O (1)

• 最坏情况 - O (log n)

我怀疑他们为什么直接用大 O 表示法写出这两种复杂性。我可以说最佳情况复杂度是Theta (1)而最坏情况复杂度是Theta (log n)吗？

标签： time-complexitybinary-search

Answer 1

是的，您可以说二进制搜索算法的最佳情况运行时间复杂度是 Theta(1)，而二进制搜索算法的最坏情况运行时间复杂度是 Theta(log n)。为了解释这一点，我们深入研究了 Big O、Big Omega 和 Big Theta 的定义，它们都是描述算法运行时间和空间复杂性的渐近符号。

当提到算法的最佳/最坏情况运行时间时，您通常指的是单个函数。Big O 表示法用于通过其上限运行时间来描述算法，而 Big Omega 表示法用于通过其下限运行时间来描述算法。

用更简单的方式说，Big O 意味着算法不能也不会比 Big O 内的函数运行得慢。Big Omega 意味着算法不能也不会比 Big Omega 内的函数运行得更快。为了使用 Big Theta 符号来描述算法的运行时间复杂度，算法的运行时间必须包含 Big O 符号和 Big Omega 符号的相同函数。

在二分搜索的情况下，最好的情况被描述为搜索算法中的第一个元素是您正在搜索的元素或项目的情况。这意味着无论发生什么，算法都只需要查看一个单一的项目。因此，这种情况可以描述为运行时间为 O(1) 和 Omega(1)。由于这两个函数是相同的，所以说二分查找算法的最佳情况运行时间是 Theta(1) 是正确的。

二进制搜索的最坏情况被描述为需要查看每个元素并且检查的最后一个元素是搜索正在寻找的元素，或者该元素根本不存在于数据结构中的情况。由于二分搜索利用分而治之的概念来查看每个元素，因此算法在最坏情况下的运行时间必须以某种形式的 (log n) 为界是微不足道的。具体来说，我们可以说它的运行时间为 O(log n) 和 Theta(log n)，因为该算法由于必须查看的元素数量而无法运行得更快或更慢在。在这种情况下，两个函数是相同的，所以说二分查找算法的最坏情况运行时间是 Theta (1) 是正确的。