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

EN

你具体问题的答案

作者是否试图说，对于n的某个值(例如300)，为求解P而编写的算法的上限是O(n^2)，而对于n(例如3000)的另一个值，同样的算法最坏的情况是Ω(n log n)？

是没有。复杂性函数不是这样工作的。)对于n的不同值，我们不讨论不同的复杂度类，复杂度指的是整个算法，而不是特定大小的算法。一种算法具有单一的时间复杂度函数T( n )，它计算输入大小n的计算所需的步骤。

在这个问题中，您得到了两条信息：

• 最坏的情况复杂度是O(n^2)
• 最糟糕的情况复杂性是Ω(n log )。

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

• 全n N1的T(n)≤c1*n^2
• 所有n个N2的T(n)≥c2*n log

换句话说，我们的T(n)是由一定时间的n log n“渐近有界”和n^2的某些常数倍n^2“渐近有界”的。它本身可以是“n log n型函数和n^2型函数之间的任何东西”。它甚至可以是n log n(因为在n^2上有界)，也可以是n^2(因为在n log n下面有界)，它可以介于n(log n)(log n) (Log N)之间。

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

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

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

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