您具体问题的答案

作者是不是想说，对于n的某个值（例如300），为求解P而编写的算法的上限是O（n^2），而对于n的另一个值（例如3000），相同的算法最坏情况是Ω（n log n）？

不是。这不是复杂度函数的工作原理。：）我们不讨论不同n值的不同复杂度类别。复杂度指的是整个算法，而不是特定大小的算法。一个算法有一个单一的时间复杂度函数T（n），它计算对于n的输入大小执行计算需要多少步骤。

在这个问题中，你会得到两条信息：

> < li>

最糟糕的情况是O(n^2)

最坏情况的复杂度为ω(n log n)

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

> 对于所有n ≥ N1，T(n) ≤ c1*n^2

T（n）≥c2*n log n对于所有n≥N2

换言之，我们的T（n）在某个常数时间n log n下“渐近有界”，在某个常量时间n ^2上“渐近有边界”。它本身可以是“介于”n log n样式函数和n^2样式函数之间的任何函数。它甚至可以是n log n（因为它在上面有n ^2的界限），也可以是n ^2（因为它下面有n log n的界限）。

与其说一个算法具有“多重最坏情况复杂性”，不如说它具有不同的行为。你看到的是一个上限和一个下限！当然，这些可能是不同的。

现在你可能有一些像这样的“奇怪”功能：

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

这个疯狂的算法确实有Skiena书中问题中指定的边界。它没有θ复杂度。这可能是你在想的，但请注意，复杂度函数没有必要如此奇怪，以便我们说上限和下限不同。要记住的是，除非明确说明，否则上限和下限并不严格。