二进制搜索算法的时间复杂度

Question

我在Cormen书中所研究的二进制Saerch算法的时间复杂性是：

• 最佳案例-O (1)
• 最坏案例-O (log n)

我的疑问是，他们为什么直接用“大O”符号写出了这两种复杂性。我可以说最佳案例复杂性是Theta (1)和最坏情况复杂性是Theta (log n)吗？

Answer 1

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

当引用算法的最佳/最坏运行时间时，通常指的是单个函数。用大O符号来描述算法的上界运行时间，用大Omega表示法来描述算法的下界运行时间。

用更简单的方法说明，Big O意味着算法不能也不会比在Big O中有界的函数运行得更慢。Big Omega意味着该算法不能而且不会比在Big Omega内的函数运行得更快。为了用Big表示法来描述算法的运行时间复杂度，该算法的运行时间必须包括对Big和Big两个符号的相同函数。

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

二进制搜索的最坏情况被描述为需要查看每个元素，而最后选中的元素是搜索要查找的元素，或者该元素根本不存在于数据结构中。由于二进制搜索使用了除法和求积的概念来查看每个元素，因此算法在最坏情况下的运行时间必须有某种形式(log )的限制，这是很简单的。具体来说，我们可以说它的运行时间为O(log )和Theta(log )，因为该算法不能运行得更快或更慢，因为它必须查看的元素的设置数。在这种情况下，这两个函数是相同的，所以说二进制搜索算法最坏的运行时间是Theta (1)是正确的。