algorithm - 渐近符号有缺陷吗？

Question

任何算法的最佳情况复杂度是算法完成其任务所需的最少时间。我们知道合并排序、快速排序等算法的最佳情况复杂度是Ω(n log(n))，它定义了这些算法的下界。
正如我们所知，在渐近符号中 -
O(n) + O(n log(n)) = O(n log(n))
还，
Ω(n) + Ω(n log(n)) = Ω(n log(n))
因此，如果在这些排序算法中，我们首先在 O(n) 时间内遍历整个数组以确定数组是否已经按升序或降序排序，那么渐近它们的平均情况和最坏情况的复杂度将保持不变。但是他们最好的案例复杂度现在变成了 Ω(n) .
从逻辑上讲，我理解这些渐近符号的方式肯定存在缺陷，否则当渐近符号被开发或流行来衡量排序算法时，肯定有人会指出这一点。我是否正确地假设这是渐近符号中的一个似是而非的缺陷，或者我是否缺少渐近符号的一些规则？

Answer 1

使用渐近复杂性作为速度的度量肯定存在问题。首先，显然常量确实很重要。 1000n通常会比 n log n 大得多，当然 n^1000远大于 2^n对于 n 的任何实际值.然而，事实证明，渐近复杂度通常是算法实际速度的一个很好的指标。
你提出的问题也是对的，但我认为不是问题。确实，一个简单的isSorted()快速排序开始时的检查将其最佳情况复杂度降低到 Θ(n) ，但人们很少关心最佳案例性能。事实上，许多常见问题的算法都可以修改为最佳情况线性，但这并不是很有用。
最后，请注意，这并不是渐进符号的真正缺陷。进行随机猜测并验证猜测是否正确(例如通过猜测数组已经排序)通常确实可以提高最佳情况的性能，而无论使用何种表示法，对平均或最坏情况的影响很小。