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

Question

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

algorithmtime-complexitybig-o

5

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

假设P是一个问题，它的最坏时间复杂度为O(n^2)，同时也有一个最坏时间复杂度为Ω(n log n)。A是一个解决P的算法。以下哪些陈述符合关于P复杂度的信息？

- A的最坏时间复杂度为O(n^2)。 - A的最坏时间复杂度为O(n^3/2)。 - A的最坏时间复杂度为O(n)。 - A的最坏时间复杂度为⍬(n^2)。 - A的最坏时间复杂度为⍬(n^3)。

一个算法如何能拥有两种最坏时间复杂度？作者是不是想说，对于某些值（例如300），编写用于解决P的算法的上限为O(n^2)，而对于另一个值（例如3000），相同的算法的最坏情况是Ω(n log n)？

- JamesWebbTelescopeAlien

2

一个人怎么可能比3米还矮，又比1米还高呢？其实是一回事。O()和Ω()只是类别。 - j_random_hacker

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ray Toal · Accepted Answer

针对你的具体问题，答案是不是。这不是复杂度函数的工作方式。我们不会因为不同的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)被某些常数时间乘以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书中问题中指定的边界。并且它没有Θ复杂度。这可能是你所考虑的，但请注意，并不需要复杂度函数如此奇怪才能说上下界不同。要记住的是，除非明确说明上下界是紧密的，否则上下界并不是紧密的。