algorithm - 算法复杂度的下限最坏情况和下限最佳情况

Question

我认为找到最坏情况的上限在大多数情况下是有意义的，因为这就是我们如何了解算法的最大运行时间的方式，并且我们可以预期给定的算法永远不会超过该限制。但是，与此相反，我们何时使用下限最坏情况和下限最佳情况分析？为什么？

我已经看到了这个问题的答案Example of algorithm which has different 最坏情况上界、最坏情况下界和最佳情况下界？但无法理解当 O 清楚地了解复杂性时，为什么需要计算 Ω 和 Θ。

编辑

---

我的问题不是关于我们在哪里使用下限，我已经看到了几个关于这个的例子。我的问题是为什么以及何时选择下限（欧米茄）而不是上限（Big O）来确定最坏的情况。

是不是因为

即使我们没有深入分析算法，下限也会立即对运行时给出一些限制？

例如，假设算法的上界最坏情况是O(n!)，我还没有深入分析算法，但已经找到了下界最坏情况Ω(2^n)，而不是更进一步，我可以得出结论，运行时复杂度最坏情况是Ω(2^n)，即，山雀已经很糟糕了，如果可能的话我们需要优化

标签： algorithmtime-complexitybig-ocomputer-sciencecomplexity-theory

Answer 1

这是一个例子。假设有人说“我有一个算法可以列出 n 元素集的所有子集”，我们想看看它需要运行多长时间。由于一个 n 元素集有 2 ^{n 个}不同的子集，因此算法的运行时间必须至少为 Ω(2 ⁿ )，因为任何比这更快的都无法列出所有这些子集。这是算法最坏情况运行时的下限，我们甚至不需要查看算法是什么来推导它。如果我们的目标是说“是的，那肯定不够快，因为我们的输入中有数千个项目”，我们可能只是在这里调用它，而无需研究算法的细节。

另一个例子是问题存在已知下限的情况。例如，如果有人发明了一种新的基于比较的排序算法，我们可以说最坏情况下的运行时间是 Ω(n log n)。它可能比这更糟，但肯定至少需要这么多时间。