最坏情况分析是否等同于渐进界限？

Question

有人能解释一下这是为什么吗？我在讲座中听到一位教授提到过这个问题。

- Programmer

---

我打赌你不知道还有另一个网站可以提问。它叫做http://cstheory.stackexchange.com/，那里的每个人都像你一样提问！ - Ilya Saunkin

@Elijah：这是一个非常可疑的说法，因为像这样的问题在那里都是不被允许的。显然，你既没有看过cstheory上提出的问题，也没有阅读它的FAQ，其中明确指出该网站仅适用于研究级别的问题。 - sepp2k

这个特定的问题有点偏离主题，你是对的。 - Ilya Saunkin

我同意sepp2k的观点。那是我没有在那里发布它的唯一原因。@Elijah：请花些时间阅读stack网站的所有常见问题解答。 - Programmer

Answer 1

这两个概念是正交的。

你可以有最坏情况下的渐近符号。如果 f(n) 表示给定算法在输入 n 的情况下所需的最坏时间，那么你可以有如 f(n) = O(n^3) 或其他最坏时间复杂度的渐近上界。

同样地，你可以有 g(n) = O(n^2 log n)，其中 g(n) 是相同算法处理（比如）大小为 n 的均匀分布（随机）输入的平均时间。

或者你可以有 h(n) = O(n)，其中 h(n) 是相同算法处理特定分布的随机输入（例如对于排序算法几乎排好序的序列）的平均时间。

渐近符号是一种“度量”。你必须指定你要计数的内容：最坏情况、最优情况、平均情况等等。

有时候，你想陈述（例如）最坏情况下的渐近下界。然后你会写下 f(n) = Omega(n^2)，来说明最坏情况下的复杂度至少为 n^2。大Omega符号与大O符号相反：f = Omega(g) 当且仅当 g = O(f)。

- Alexandre C.

Answer 2

以 快速排序为例，快速排序的每个递归调用n的运行时复杂度为T(n)。

如果未排序的输入列表在每次调用中被分成两个大小相等的子列表（每个列表大小为（n-1）/2），则在“最佳情况”下：

T(n) = O(n) + 2 T[(n-1)/2]

解决T(n)得到O(n log n)。如果划分不完美，两个子列表大小不相等，即：

T(n) = O(n) + T(k) + T(n - 1 - k)，

即使k=1，我们仍然可以获得O(n log n)，只是具有更大的常数因子。这是因为在处理输入列表时，快速排序的递归调用数量呈指数级增长，只要k>0。

但是，在“最坏情况”下，不会对输入列表进行任何分割，即：

T(n) = O(n) + T(0) + T(n - 1) = O(n) + O(n-1) + T(n-1) + T(n-2) ... .

例如，如果我们将排序列表的第一个元素作为枢轴元素，则会发生这种情况。

在这里，T（0）表示其中一个结果子列表为零，因此不需要计算时间（因为子列表具有零个元素）。 剩余的所有负载T（n-1）都需要用于第二个子列表。 在这种情况下，我们获得O（n²）。

如果算法没有最坏情况，它不仅是O [f（n）]，而且还是o [f（n）]（大O与小o符号）。

- GK80

---

你最后一句话是错的。O和o与算法的最坏情况运行时间是否相关。我不确定你是否理解o的含义（我认为你将其与Θ混淆了，它也与最坏情况无关，但确实告诉你是否有“最紧密”的界限）。例如，遍历长度为n的数组所需的时间为O(n)和Θ(n)，但不是o(n)。 - sepp2k

是的，我想我把它和\Theta混淆了--而且，是的，在第二次思考时，它也与此无关。但是，无论如何，正如答案所述，O-符号只是一种度量方式，并不指定度量的内容。这是一个更为严谨的解释。 - GK80

Answer 3

渐近界限是操作次数趋向无限时的期望行为。在数学上，它就是当n趋向于无穷大时的极限。然而最坏情况行为适用于有限的操作次数。

- Navi