2^n 和 n*2^n 是否具有相同的时间复杂度？

为了回答这个问题，您必须查看大 O (O) 的正式定义。

定义是当且仅当极限 limsupx → ∞ (f(x)/g(x)) 存在即不是无穷大时，f(x) 属于 O(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))。

---

快速查看 n⋅2ⁿ 更大的方法是更改变量。让m = 2ⁿ。然后是 n⋅2ⁿ = ( log₂m )⋅m（在 m = 2ⁿ 两边取以 2 为底的对数得到 n = log₂m），您可以很容易地证明 m log₂m 比 m 增长得更快。

---

我同意 n⋅2ⁿ 不在 O(2ⁿ) 中，但我认为它应该更明确，因为限制高级用法并不总是成立。

根据 Big-O 的正式定义：如果存在常量 c > 0 和 n₀ ≥ 0，则 f(n) 在 O(g(n)) 中，这样对于所有 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ⁿ 慢。

---

我不反对其他说 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)ⁿ，并且对于任何 n，它都小于 1。

所以 2ⁿ 比 n⋅2ⁿ 增长得慢，最后一个又比 2.000001ⁿ 增长得慢。但他们三个都呈指数级增长。

---

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

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

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

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

---

非常简单的答案是“不”

请参阅 2^n 和 n.2^n

如任何 n>0 所见的 n.2^n > 2^n

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

 n.log(2)    <    n.log(2) + log(n) 

因此通过两种类型的分析，即

使用 log 替换数字

我们看到 n.2^n 大于 2^n 可见

所以如果你得到一个等式

O ( 2^n + n.2^n ) 可以替换为 O ( n.2^n)

---