algorithm - 渐近符号有缺陷吗？

任何算法的最佳情况复杂度是算法完成其任务所需的最短时间。我们知道合并排序、快速排序等算法的最佳情况复杂度是 Ω(n log(n))，它定义了这些算法的下限。

正如我们所知，在渐近符号中 -

O(n) + O(n log(n)) = O(n log(n))

还，

Ω(n) + Ω(n log(n)) = Ω(n log(n))

因此，如果在这些排序算法中，我们首先在 O(n) 时间内遍历整个数组以确定该数组是否已经按升序或降序排序，那么它们的平均情况和最坏情况复杂度将渐近保持不变。但是他们最好的情况复杂性现在将变为Ω(n)。

从逻辑上讲，我理解这些渐近符号的方式肯定存在缺陷，否则当渐近符号正在开发或流行以测量排序算法时，肯定有人会指出这一点。我是否正确假设这是渐近符号中的一个似是而非的缺陷，还是我错过了一些渐近符号规则？

标签： algorithmsortingtime-complexitycomplexity-theory

使用渐近复杂度作为速度度量肯定存在问题。首先，显然常数很重要。1000n往往会比大得多n log n，而且肯定n^1000比2^n任何实际价值都要大得多n。然而，事实证明，渐近复杂度通常是算法实际速度的一个相当好的指标。

你提出的问题也是正确的，但我不认为这是一个问题。确实，isSorted()快速排序开始时的简单检查会将其最佳案例复杂度降低到Θ(n)，但很少有人关心最佳案例性能。事实上，许多常见问题的算法都可以修改为最佳情况线性，但这并不是很有用。

最后，请注意，这并不是渐近符号的真正缺陷。进行随机猜测并验证猜测是否正确（例如通过猜测数组已经排序）通常确实可以提高最佳情况的性能，而对平均或最坏情况的影响很小，无论使用哪种表示法。