2 ^ n和n*2 ^ n在同一时间复杂度？

Question

2 ^ n和n*2 ^ n在同一时间复杂度？

mat*_*y-d 177 algorithm complexity-theory big-o time-complexity

我发现时间复杂度的资源还不清楚何时可以忽略时间复杂度方程中的项,特别是非多项式的例子.

我很清楚,给定n ² + n + 1 形式的东西,最后两个术语是无关紧要的.

具体来说,给定两个分类,2 ⁿ和n*(2 ⁿ),是第二个与第一个相同的顺序？额外的n乘法是否重要？通常资源只是说x ⁿ处于指数状态并且增长得更快......然后继续前进.

我可以理解为什么它不会因为2 ⁿ将大大超过n,但因为它们没有被加在一起,所以在比较两个方程时它会很重要,实际上它们之间的差异总是n的因子,这似乎至少可以说是重要的.

Answer 1

izo*_*ica 229

你必须转到大O(O)的正式定义才能回答这个问题.

定义f(x)属于O(g(x))if且仅当限制存在时,即不是无穷大.简而言之,这意味着存在一个常数,使得值永远不会大于.limsup_{x ? ?} (f(x)/g(x))Mf(x)/g(x)M

如果你的问题让我们放手.然后是这将仍增长无限.因此不属于.f(n) = n ? 2ⁿg(n) = 2ⁿf(n)/g(n)nf(n)O(g(n))

限制不一定存在; 对于足够大的x,该比率只需要超过常数.例如,2 + sin(x)在O(1)中,但是(2 + sin(x))/ 1不接近x->无穷大的极限. (43认同)
@IvayloStrandjev请注意您的简短描述不正确.对于足够大的"x",这必须是真的,而不是对于所有的"x"值. (11认同)
有关更容易阅读的定义,请参阅[此处](http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition) (5认同)
从形式上讲,你不能取"O(f(x)/ g(x))"的限制; big-O通知是一组函数的简写,而不是可以限制其值的单个函数.但是,我认为*如果`lim(x-> infinity)f(x)/ g(x)`存在,你可以证明`f(x)= O(g(x))`. (3认同)
使用`lim sup`而不是`lim`来定义是正确的. (2认同)
@ K.Steff你当然是对的.我仍然不会在我的答案中加入这种变化,因为当我们考虑复杂性函数时它几乎不会重要.我想尽可能全面地回答这个问题.在所有实际例子中,我都可以认为f(x)/ g(x)永远不会是无穷大的(对于正x),因此我所写的是准确的.我不想写`足够大的x',因为我将不得不解释'足够大'的意思,这将增加很多复杂性. (2认同)

Answer 2

che*_*ner 85

快速查看n?2?更大的方法是更改变量.我们m = 2?.然后n?2? = ( log?m )?m(在m = 2?给出的两侧取基数为2的对数n = log?m),你可以很容易地显示出m log?m增长得快m.

谢谢!在我看来,这是最好的答案.基于正式定义的证明是正确的,但是如果你有某种绊脚石可以克服,那么一个非常舒适和熟悉的类比将能够做到最好,最快. (3认同)
这是一个懒惰的缩写.在计算机科学中,它往往意味着基础2,因为它主要来自分而治之的策略.在big-O表示法中,它可以表示任何东西,因为数字的base-x对数与其base-y对数不同,只是一个常数因子,而不管x和y. (3认同)
我要回顾一下,`lg`是基数为10的对数的ISO表示法,而不是在讨论渐近运行时最常用的基本不可知用法.见http://en.wikipedia.org/wiki/Logarithm#Particular_bases (3认同)
好吧，当然，但我不明白为什么 m log m 比 m 增长得更快，而不是 n 2^n 比 2^n 增长得更快。 (2认同)

Answer 3

zpr*_*zpr 10

我同意n?2?不存在O(2?),但我认为它应该更明确,因为限制优越使用并不总是成立.

通过大O的正式定义:f(n)是O(g(n))的,如果存在常数c > 0,并n? ? 0使得对所有n ? n?我们有f(n) ? c?g(n).可以容易地证明,对于不存在这样的常量f(n) = n?2?和g(n) = 2?.但是,它可以显示g(n)在O(f(n)).

换句话说,n?2?更低的界限2?.这很直观.虽然它们都是指数级的,因此在大多数实际情况下同样不太可能使用,但我们不能说它们的顺序相同,因为它们2?必然会慢于n?2?.

Answer 4

And*_*rey 5

我不反对其他说n?2?增长速度比2?. 但n?2?增长仍然只是指数级的。

当我们谈论算法时，我们经常说时间复杂度呈指数增长。因此，我们认为2?, 3?, e?, 2.000001?, 或我们n?2?是具有指数增长的同一组复杂性。

为了给它一点数学意义，我们考虑一个函数f(x)，如果存在这样的常数c > 1，那么它就会呈指数增长（不快于）。f(x) = O(c^x)

因为n?2?常数c可以是任何大于的数2，让我们取3。然后：

n?2? / 3? = n ? (2/3)?这比1任何n.

所以2?长得比n?2?，最后依次长得比2.000001?。但它们三个都呈指数级增长。

归档时间：	11 年，9 月前
查看次数：	21745 次
最近记录：	10 年，7 月前