algorithm - 二分查找的复杂性

Question

我正在观看 Berkley Uni 在线讲座并停留在下面。

问题:假设您有一组已排序的 CD。您想要查找标题以“Best Of”开头的 CD 列表。

解决方案:我们将使用二进制搜索找到第一个“Best Of”的情况，然后打印直到图 block 不再是“Best Of”

附加问题:找出该算法的复杂度。

上界:二分搜索上界是 O(log n)，所以一旦找到它，我们就打印出 k 个标题。所以它是 O(logn + k)

下界:二分搜索下界是 Omega(1)，假设我们很幸运并且记录标题是中间标题。在这种情况下是 Omega(k)

我是这样分析的。

但是在讲座中，讲师使用了最好的情况和最坏的情况。我有两个问题:

1. 为什么需要使用最佳情况和最坏情况，big-O 和 Omega 不是被认为是算法可以执行的最佳情况和最坏情况吗？

2. 他的分析是 最坏情况:Theta(logn + k)
   最佳情况:Theta (k)

   如果我使用最坏情况的概念来指代数据并且与算法无关那么是的，他的分析是正确的。这是因为假设最坏的情况(CD 标题在最后或找不到)然后 Big O 和 Omega 都是 log n 在那里它是 theta(log n +k)。

   假设你不做“best case”和“worst case”，那你怎么分析算法呢？我的分析对吗？

Answer 1

Why need to use best case and worst case, aren't big-O and Omega considered as the best and worst cases the algorithm can perform?

不，O 和 Ω 符号仅描述函数的边界，该函数描述算法实际行为的渐近行为。这是一个很好的

• Ω 描述下界:f(n) ∈ Ω(g(n)) 表示 f(n) 的渐近行为em>n) 不小于 g(n)·k 对于某些正 k , 所以 f(n) 总是至少和 g(n)·k 一样多。<
• O 描述上限:f(n) ∈ Ø(g(n)) 表示 f(n) 的渐近行为em>n) 不超过 g(n)·k 对于某些正 k ，所以 f(n) 总是至多等于 g(n)·k。<

这两个可以应用于二进制搜索的最佳情况和最坏情况:

• 最佳情况:您看到的第一个元素就是您正在寻找的元素
  • Ω(1):你需要至少一次查找
  • O(1):你最多需要一次查找
• 最坏情况:元素不存在
  • Ω(log n):您需要至少 log n 步，直到您可以说您正在寻找的元素不是出席
  • O(log n):您需要最多 log n 步，直到您可以说您正在寻找的元素不是出席

您看，Ω 和 Ο 值是相同的。在这种情况下，您可以说最佳情况下的紧界是 Θ(1)，最坏情况下是 Θ(log n)。

但通常我们只想知道上界或紧界，因为下界没有太多实用信息。

Assuming you do not do "best case" and "worst case", then how do you analyze the algorithm? Is my analysis right?

是的，您的分析似乎是正确的。