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

Question

我最近遇到了一个 argument/debate，我正在尝试对正确的解决方案做出明确的判断。

众所周知n! grows very quickly，但是多快，足以"hide"所有可能添加到它的附加常量？

假设我有这个愚蠢而简单的程序（没有特定语言）：

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

Bob 声明："This program's complexity is obviously O(n)O(n)O(n!) = O(n!n^2) = O((n+2)!)."

爱丽丝 回复："I agree with you bob, but actually it would be sufficient if you said that the complexity is O(n!) since O(n!n^k) = O(n!) for any k >= 1 constant."

爱丽丝对鲍勃分析的记录是否正确？

Answer 1

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

回忆一下使用极限时大 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!)

中

Answer 2

Amit 解决方案是完美的，我只会添加更多"human" 解决方案，因为对于初学者来说理解定义可能很困难。

定义基本上是说 - 如果您增加值 n 并且方法 f(n) 和 g(n) 不同 "only" k 次，其中k 是常数，不会改变（例如 g(n) 总是高 ~100 倍，无论是 n=10000 还是 n=1000000），那么这些函数具有相同的复杂度。

如果 g(n) 比 n=10000 高 100 倍，n=1000000 高 80 倍，那么 f(n) 的复杂度更高！因为随着 n 越来越大，f(n) 最终会在某个时候达到 g(n)，然后与 g(n) 相比，它会越来越大。在复杂性理论中，您感兴趣的是它将如何以 "infinity"（或更可想象的 n 的极高值）结束。

如果比较 n! 和 n!*n^2，您可以看到，对于 n=10，第二个函数的值高 10^2=100 倍。对于 n=1000，它的价值高出 1000^2=1000000 倍。正如您想象的那样，差异会越来越大。

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

Which Big-O grows faster asymptotically

big-o

time-complexity

asymptotic-complexity