big-o - 哪个 Big-O 渐近增长得更快

Question

我最近陷入了争论/辩论中，我试图对正确的解决方案做出明确的判断。

众所周知， n! grows very quickly ，但究竟有多快，足以“隐藏”可能添加到其中的所有其他常量？

让我们假设我有这个愚蠢而简单的程序(没有特定的语言):

for i from 0 to n! do:
    ; // nothing

鉴于输入是 n ，那么这个的复杂度显然是 O(n!) (甚至 ϴ(n!) 但这与此处无关)。

现在让我们假设这个程序:

for i from 0 to n do:
    for j from 0 to n do:
        for k from 0 to n! do:
            ; // nothing

鲍勃 声称:“这个程序的复杂性显然是 O(n)O(n)O(n!) = O(n!n^2) = O((n+2)!)。”

爱丽丝 回答:“我同意你的观点，但实际上，如果你说复杂性是 O(n!) 就足够了，因为 O(n!n^k) = O(n!) 对于任何 k >= 1 常数。”

爱丽丝在她对鲍勃分析的笔记中是否正确？

Answer 1

爱丽丝错了，鲍勃是对的。

回想一下使用 limit 时大 O 符号的等效定义:

f(n) is in O(g(n)) iff 
lim_n->infinity: f(n)/g(n) < infinity

对于任何 k>0 :

lim_n->infinity: (n!*n^k) / n! = lim_n->infinity n^k = infinity

因此， n!*n^k不在 O(n!)