算法如何具有两种最坏情况的复杂性？

Question

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

让P成为一个问题.P的最坏情况时间复杂度是O(n ^ 2).P的最坏情况时间复杂度也是Ω(n log n).设A是一个求解P的算法.以下陈述的哪个子集与关于P的复杂性的信息一致？

• A具有最坏情况时间复杂度O(n ^ 2).
• A具有最坏情况时间复杂度O(n ^ 3/2).
• A具有最坏情况时间复杂度O(n).
• A具有最坏情况时间复杂度⍬(n ^ 2).
• A具有最坏情况时间复杂度⍬(n ^ 3).

算法如何具有两个最坏情况时间复杂度？作者试图说,对于某些值n(例如300),用于求解的算法的上限P是O(n ^ 2)的量级,而对于另一个值n(例如3000),同样的算法最坏的情况是Ω(n log n)？

Answer 1

您具体问题的答案

作者试图说,对于n的某些值(例如300),为解决P而编写的算法的上界是O(n ^ 2)的量级,而对于n的另一个值(例如,例如3000),相同的算法最坏的情况是Ω(n log n)？

是没有.这不是复杂功能的工作方式.:)我们不讨论不同n值的不同复杂性类.复杂性指的是整个算法,而不是特定大小的算法.算法具有单个时间复杂度函数T(n),其计算对于n的输入大小执行计算所需的步数.

在这个问题中,您将获得两条信息:

• 最坏的情况是O(n ^ 2)

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

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

• 对于所有n≥N1,T(n)≤c1*n ^ 2

• 所有n≥N2的T(n)≥c2*n log n

换句话说,我们的T(n)通过某个常数时间n log n"渐近有界"并且"渐近地限制在上面"一些常数n ^ 2.它本身可以是n log n样式函数和n ^ 2样式函数之间的任何东西.它甚至可以是n log n(因为它高于n ^ 2)或者它可以是n ^ 2(因为它在n log n之下有界.它可以介于两者之间,如n(log n)(log N).

并不是说算法具有"多个最坏情况复杂性",因为它具有不同的行为.你看到的是上限和下限!当然,这些可以是不同的.

现在有可能你有一些像这样"奇怪"的功能:

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

这个疯狂的算法确实具有Skiena书中问题中指定的界限.并且它没有Θ复杂性.这可能是你正在考虑的事情,但请注意,为了让我们说上限和下限不同,复杂性函数没有必要这么奇怪.需要记住的是,除非明确说明,否则上限和下限并不严格.