我正在观看Berkley Uni的在线讲座并坚持下面的内容 .
Problem ：假设您有一个已经排序的CD集合 . 您要查找 Headers 以"Best Of."开头的CD列表
Solution ：我们将使用二分搜索来查找"Best Of"的第一个案例，然后我们打印直到瓷砖不再"Best Of"
Additional question ：找出此算法的复杂性 .
上限：二进制搜索上限是O（log n），所以一旦我们找到它，那么我们打印让我们说k Headers . 所以它是O（logn k）
下限：二进制搜索下限是Omega（1），假设我们很幸运，并且记录 Headers 是中间 Headers . 在这种情况下，它是欧米茄（k）
这是我分析它的方式 .
但在讲座中，讲师使用了最好的案例和最坏的案例 . 我有两个问题：
-
为什么需要使用最佳情况和最坏情况，不是大O和Omega被认为是算法可以执行的最佳和最差情况？
-
他的分析是最糟糕的案例：Theta（logn k）
最佳案例：Theta（k）
如果我使用最坏情况的概念来指代数据并且与算法无关，那么他的分析是正确的 . 这是因为假设最坏的情况（CD Headers 到底或未找到）那么Big O和Omega都是log n，那里是theta（log n k） .
假设您没有做“最佳案例”和“最坏情况”，那么您如何分析算法？我的分析是对的吗？
2 回答
不，Ο和Ω表示法仅描述描述算法实际行为的渐近行为的函数的边界 . 这是一个很好的
Ω描述 lower bound ：f（n）∈Ω（g（n））表示对于某些正k，f（n）的渐近行为是 not less than g（n）·k，因此f（n）是 always at least as much as g（n ）·K .
Ο描述 upper bound ：f（n）∈Ο（g（n））表示对于某些正k，f（n）的渐近行为是 not more than g（n）·k，因此f（n）是 always at most as much as g（n ）·K .
这两个可以应用于二进制搜索的最佳情况和最坏情况：
最佳案例：你看的第一个元素就是你要找的元素
Ω（1）：您至少需要一次查找
Ο（1）：您最多需要一次查找
最坏的情况：元素不存在
Ω（log n）：您至少需要log n步，直到您可以说您要查找的元素不存在
Ο（log n）：您最多需要log n步骤，直到您可以说您要查找的元素不存在
你看，Ω和Ο值是相同的 . 在这种情况下，您可以说最佳情况的紧密界限是Θ（1），最坏的情况是Θ（log n） .
但通常我们只想知道上限或紧束，因为下界没有太多实用信息 .
是的，您的分析似乎是正确的 .
对于您的第一个问题，算法的最佳案例运行时，算法的最坏情况运行时，大O和大Ω符号之间存在差异 . 算法的最佳和最差情况运行时是具有精确值的实际数学函数，它们告诉您算法将执行的最大和最小工作量 . 为了描述这些函数的增长率，我们可以使用big-O和big-Ω表示法 . 但是，可以描述具有大Ω符号的函数的最佳情况行为或具有大O符号的最坏情况 . 例如，我们可能知道函数的最坏情况运行时可能是O（n2），但实际上并不知道哪个函数是O（n2）最坏情况的行为 . 如果我们想要对最坏情况行为进行上限以便我们知道在这种情况下最坏情况行为实际上是Θ（n），那么可能会发生这种情况，在这种情况下O（n2）是一个不好的上限，但是说最坏情况的行为是O（n2）在这种情况下表明它不是't terrible. Similarly, we might say that the best-case behavior of an algorithm is Ω(n), for example, if we know that it must do at least linear work but can'告诉它是否必须做更多的事情 .
关于你的第二个问题，对算法的最坏情况和最佳情况行为的分析完全取决于输入数据的结构，并且通过展示一些特定的族来做最坏情况分析是完全合理的 . 输入（注意它必须是一系列输入，而不仅仅是一个输入，因为我们需要渐近绑定）并显示该算法必须在该输入上运行不良 . 您可以以相同的方式进行最佳案例分析 .
希望这可以帮助！