哪个Big-O渐近增长更快 [英] Which Big-O grows faster asymptotically

问题描述

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

I have gotten into an argument/debate recently and I am trying to get a clear verdict of the correct solution.

众所周知， n!增长非常快，但实际上有多快 ，足以隐藏"可能添加到其中的所有其他常量?

It is well known that n! grows very quickly, but exactly how quickly, enough to "hide" all additional constants that might be added to it?

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

Let's assume I have this silly & simple program (no particular language):

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

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

Given that the input is n, then the complexity of this is obviously O(n!) (or even ϴ(n!) but this isn't relevant here).

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

Now let's assume this program:

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

Bob 声称:该程序的复杂性显然是 O(n)O(n)O(n!) = O(n!n^2) = O((n+2)!) ."

Bob claims: "This program's complexity is obviously O(n)O(n)O(n!) = O(n!n^2) = O((n+2)!)."

爱丽丝回答:鲍勃，我同意，但是如果您说由于 O(n!n^k) = O(n!) 表示任何k >= 1常量."

Alice responds: "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."

爱丽丝在鲍勃的分析记录中对吗?

Is Alice right in her note of Bob's analysis?

推荐答案

爱丽丝(Alice)是错误的，鲍勃(Bob)是正确的.

Alice is wrong, and Bob is right.

在使用limit时，调用与大O表示法等效的定义:

Recall an equivalent definition to big O notation when using limit:

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!)

这篇关于哪个Big-O渐近增长更快的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！