2^n 和 n*2^n 的时间复杂度相同吗？

Question

我发现的关于时间复杂度的资源不清楚何时可以忽略时间复杂度方程中的项，特别是对于非多项式示例。

我很清楚，给定 n² + n + 1 形式的东西，最后两项是微不足道的。

具体来说，给定两个分类 2ⁿ 和 n*(2ⁿ)，第二个与第一个的顺序是否相同？额外的 n 乘法有关系吗？通常资源只是说 xⁿ 呈指数增长并且增长得更快......然后继续。

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

Answer 1

为了回答这个问题，你必须了解大O的正式定义。

定义是，当且仅当极限

f(x)

存在，即不是无穷大时，

O(g(x))

属于

limsupx → ∞ (f(x)/g(x))

。简而言之，这意味着存在一个常数

M

，使得

f(x)/g(x)

的值永远不会大于

M

。

对于您的问题，让

f(n) = n ⋅ 2n

并让

g(n) = 2n

。那么

f(n)/g(n)

就是

n

，它仍然会无限增长。因此

f(n)

不属于

O(g(n))

。

Answer 2

查看

n⋅2ⁿ

变大的快速方法是更改变量。让

m = 2ⁿ

。然后

n⋅2ⁿ = ( log₂m )⋅m

（在

m = 2ⁿ

两边取以 2 为底的对数得到

n = log₂m

），你可以很容易地证明

m log₂m

比

m

增长得更快。

Answer 3

我同意

n⋅2ⁿ

不在

O(2ⁿ)

中，但我认为它应该更明确，因为限制高级用法并不总是成立。

根据 Big-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

我不反对其他答案，即

n⋅2ⁿ

比

2ⁿ

增长得更快。但

n⋅2ⁿ

的增长仍然只是指数级的。

当我们谈论算法时，我们经常说时间复杂度呈指数增长。 因此，我们认为

2ⁿ

、

3ⁿ

、

eⁿ

、

2.000001ⁿ

，或者我们的

n⋅2ⁿ

是同一组复杂性呈指数增长的。

为了给它一点数学意义，我们考虑一个函数

f(x)

，如果存在这样的常数

c > 1

，即

f(x) = O(cx)

，则呈指数增长（不快于）。

对于

n⋅2ⁿ

，常数

c

可以是任何大于

2

的数字，我们以

3

为例。然后：

n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿ

，对于任何

1

，这都小于

n

。

所以

2ⁿ

的增长速度比

n⋅2ⁿ

慢，最后一个又比

2.000001ⁿ

增长慢。但它们三个都呈指数级增长。

Answer 5

您问“第二个与第一个的顺序相同吗？附加的 n 乘法重要吗？”这是两个不同的问题，有两个不同的答案。

n 2^n 的渐近增长速度比 2^n 快。这就是那个问题的答案。

但是你可能会问“如果算法 A 需要 2^n 纳秒，算法 B 需要 n 2^n 纳秒，那么我可以在一秒/分钟/小时/天/月/年内找到解决方案的最大 n 是多少？答案是 n = 29/35/41/46/51/54 与 25/30/36/40/45/49 在实践中没有太大区别。

在这两种情况下，在时间 T 内可以解决的最大问题的大小都是 O (ln T)。

Answer 6

非常简单的答案是“不”

参见

2^n

 和 

n.2^n

如所见

n.2^n > 2^n

 对于任何 

n>0

或者你甚至可以通过在两侧应用日志来做到这一点，然后你就得到了

n.log(2) < n.log(2) + log(n) 因此通过两种类型的分析

1. 替换数字

2. 使用日志

我们看到

n.2^n

 大于 

2^n

 可见

所以如果你得到一个像这样的方程

O ( 2^n + n.2^n )

 可以替换为 

O ( n.2^n)