algorithm - 算法的最坏情况时间复杂度与其上限之间的关系/区别是什么？

Question

算法的最坏情况时间复杂度与其上限之间的关系/区别是什么？

Answer 1

“上限”这个词不是很清楚，因为它可能指的是两种可能的东西:

1. 算法的上限 - 算法永远不会运行得比它“慢”的界限。这基本上是它在最坏情况下的表现，所以如果这就是您的意思 - 答案很简单。

2. big-O 表示法，它提供了特定分析下算法复杂性的上限。大 O 表示法是一组函数，可以应用于算法的任何分析，包括最坏情况、平均情况，甚至最好情况。

我们以Quick Sort为例举个例子。

据说快速排序具有 O(n^2) 最坏情况性能和 O(nlogn) 平均情况性能。一个算法怎么会有两个复杂度？很简单，代表平均情况分析的函数和代表最坏情况的函数是完全不同的函数——我们可以对它们分别应用大O符号，没有任何限制。

此外，我们甚至可以将其应用于最佳情况。考虑一个快速排序的小优化，它首先检查数组是否已经排序，如果是 - 它立即停止。这实际上是 O(n) 操作，并且有一些输入会提供这种行为 - 所以我们现在可以说算法的最佳情况复杂度是 O(n)