相关疑难解决方法(0)

我正在观看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).

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