一个算法怎么会有两个最坏情况的复杂度？

Question

Steven Skiena 的算法设计手册第 1 章练习有这个问题：

Let P be a problem. The worst-case time complexity of P is O(n^2) . The worst-case time complexity of P is also Ω(n log n) . Let A be an algorithm that solves P. Which subset of the following statements are consistent with this information about the complexity of P?

A has worst-case time complexity O(n^2) .

A has worst-case time complexity O(n^3/2).

A has worst-case time complexity O(n).

A has worst-case time complexity ⍬(n^2).

A has worst-case time complexity ⍬(n^3) .

一个算法怎么会有两个最坏情况的时间复杂度？作者是否试图说对于 n 的某个值（例如 300），为解决 P 而编写的算法的上限是 O(n^2) 的顺序，而对于 n（例如 3000）相同算法最坏情况是 Ω(n log n)?

Answer 1

您具体问题的答案

is the author trying to say that for some value of n (say e.g. 300) upper bound for algorithm written for solving P is of the order of O(n^2) while for another value of n (say e.g. 3000) the same algorithm worst case was Ω(n log n)?

是没有。这不是复杂性函数的工作方式。 :) 我们不讨论不同的 n 值的不同复杂度类。复杂度是指整个算法，而不是特定大小的算法。一个算法有一个单一的时间复杂度函数T(n)，它计算需要多少步来执行输入大小n的计算。

题中给出了两条信息：

最坏情况复杂度为O(n^2)
最坏情况复杂度为Ω(n log n)

这意味着我们可以选择常数 c1、c2、N1 和 N2，这样对于我们的算法函数 T(n)，我们有

T(n) ≤ c1*n^2 对于所有 n ≥ N1
T(n) ≥ c2*n log n 对于所有 n ≥ N2

换句话说，我们的 T(n) 是 "asymptotically bounded below" 某个常数时间 n log n 和 "asymptotically bounded above" 某个常数时间 n^2。它本身可以是任何东西 "between" n log n 样式函数和 n^2 样式函数。它甚至可以是 n log n（因为它的上界是 n^2）或者它可以是 n^2（因为它的下界是 n log n。它可以介于两者之间，比如 n(log n)(log n).

算法具有 "multiple worst case complexities" 并不是因为它有不同的行为。你看到的是上限和下限！当然，这些可以有所不同。

现在可能你有一些像这样的"weird"功能：

def p(n):
    if n is even:
        print n log n stars
    else:
        print n*2 stars

这个疯狂的算法确实有 Skiena 书中问题中指定的界限。而且它没有 Θ 复杂度。这可能正是您所考虑的，但请注意，为了让我们说上限和下限不同，复杂度函数不必如此奇怪。要记住的是，除非明确说明，否则上限和下限并不是紧。

一个算法怎么会有两个最坏情况的复杂度？

How can an algorithm have two worst case complexities?

algorithm

big-o

time-complexity