二元搜索的复杂性

Question

我正在观看Berkley Uni的在线讲座并坚持下面的内容.

问题:假设您有一个已经排序的CD集合.您要查找标题以"Best Of"开头的CD列表.

解决方案:我们将使用二进制搜索来查找"Best Of"的第一个案例,然后我们进行打印,直到该块不再是"Best Of"

附加问题:找出此算法的复杂性.

上限:二进制搜索上限是O(log n),所以一旦我们找到它,那么我们打印让我们说k标题.所以它是O(logn + k)

下限:二进制搜索下限是Omega(1),假设我们很幸运,并且记录标题是中间标题.在这种情况下,它是欧米茄(k)

这是我分析它的方式.

但在讲座中,讲师使用了最好的案例和最坏的案例.我有两个问题:

1. 为什么需要使用最佳情况和最坏情况,不是大O和欧米茄被认为是算法可以执行的最佳和最差情况？

2. 他的分析是最糟糕的案例:Theta(logn + k)
   最佳案例:Theta(k)

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

   假设您没有做"最佳案例"和"最坏情况",那么您如何分析算法？我的分析是对的吗？

Answer 1

为什么需要使用最佳情况和最坏情况,不是大O和欧米茄被认为是算法可以执行的最佳和最差情况？

不,Ο和Ω表示法仅描述描述算法实际行为的渐近行为的函数的边界.这是一个很好的

• Ω描述下界:F(Ñ)∈Ω(克(Ñ))是指F(的渐近行为Ñ)是不小于克(ñ)· ķ一些阳性ķ,因此f(Ñ)是始终在至少与 g(n)· k一样多.
• Ο描述了上界:F(Ñ)∈Ο(克(Ñ))是指F(的渐近行为Ñ)是不超过克(ñ)· ķ一些阳性ķ,因此f(Ñ)是始终在最多与 g(n)· k.

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

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

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

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

假设您没有做"最佳案例"和"最坏情况",那么您如何分析算法？我的分析是对的吗？

是的,您的分析似乎是正确的.