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

Question

我在时间复杂度方面找到的资源对于何时可以忽略时间复杂度方程中的项不是很清楚，尤其是对于非多项式的例子。

对于形如n² + n + 1的表达式，最后两项可以忽略不计。

具体来说，对于两个分类：2ⁿ和n*(2ⁿ)，第二个分类是否与第一个分类相同？那里的额外乘以n是否重要？通常的资源只是说xⁿ是指数级别的，增长速度快得多……然后就过去了。

我能理解为什么不需要考虑乘以n，因为2ⁿ会大大超过n，但是因为它们没有被加在一起，所以在比较这两个方程时它们的差异将始终是n的一个因素，这似乎至关重要。

- matty-d

---

据我看来，尽管NLogN被认为比N慢，但大多数人并不关心具体有多慢，因此可以说N2^N比2^N慢，但并不“足够慢”以引起人们的关注。 - Jack

直到你必须使用nlogn而不是n对数排序处理亿万条记录时，大多数人才会真正关心排序时间的差异，但大多数人并不太在意。 - C.B.

实际上，n! = o((n+1)!)，也就是说，从渐近意义上讲，它增长得严格较慢。 - chepner

请注意，这与复杂性理论无关，仅涉及渐进分析。此类问题可能更适合在 [cs.SE] 上提出。 - Raphael

@C.B.：一个时间复杂度为O(N)但常数比O(NlgN)算法大30倍的算法，在任何合理的N值下都不可能显著优于O(NlgN)算法。 - supercat

Answer 1

您需要查看大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))。

- Ivaylo Strandjev

---

若要阅读更易懂的定义，请点击这里。 - Alden

严格来说，你不能对 O(f(x)/g(x)) 取极限；大O符号是一组函数的缩写，而不是可以取值的单个函数。然而，我 认为 如果 lim(x->infinity) f(x)/g(x) 存在，你可以证明 f(x) = O(g(x))。 - chepner

极限不一定存在；只需在足够大的x值上，比值被一个常数所限制即可。例如，2+sin(x)是O(1)级别的，但是当x无限增大时，(2+sin(x))/1并没有趋近于一个极限值。 - user2357112

定义使用 lim sup 而不是 lim 将是正确的。 - David Eisenstat

请注意，@IvayloStrandjev的简短描述是不正确的。这对于足够大的 x 是真实的，而不是所有的 x 值都是如此。 - K.Steff

Answer 2

一个快速查看 n⋅2ⁿ 更大的方法是进行变量替换。令 m = 2ⁿ。然后有 n⋅2ⁿ = ( log₂m )⋅m（对 m = 2ⁿ 两边取以2为底的对数得到 n = log₂m），并且您可以轻松证明 m log₂m 比 m 的增长更快。

- chepner

---

谢谢！在我看来，这是最好的答案。基于正式定义的证明是正确的，但是如果你遇到了某种障碍需要克服，一个非常舒适和熟悉的比喻会最好、最快地完成任务。 - John P

愚蠢的问题，lg是什么？以2为底的对数？ - Pierre Arlaud

这是一个懒惰的缩写词。在计算机科学中，它通常表示基础为2，因为这大多数情况下是分治策略产生的结果。在大O符号中，它可以代表任何东西，因为一个数字的以x为底的对数与以y为底的对数只相差一个常数因子，不论x和y是什么。 - chepner

回顾起来，我应该指出 lg 是表示以10为底的对数的 ISO 表示法，而不是讨论渐近运行时间时最常用的与底数无关的表示法。详见 http://en.wikipedia.org/wiki/Logarithm#Particular_bases - chepner

好的，没问题。但我不理解为什么 m log m 的增长速度比 m 更快比 2^n 的增长速度还要更显然。 - djechlin

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ⁿ慢。

- zpr

---

f(n) = 2*2^n 我认为你的意思是 n*2^n？ - tobias_k

Answer 4

我不会反驳其他答案说 n⋅2ⁿ 的增长速度比 2ⁿ 更快。但是 n⋅2ⁿ 增长仍然只是指数级别的。

当我们谈论算法时，通常会说时间复杂度呈指数级增长。因此，我们认为 2ⁿ、3ⁿ、eⁿ、2.000001ⁿ 或者我们的 n⋅2ⁿ 属于同一组具有指数级增长的复杂度。

为了让它更具数学意义，我们认为如果存在一个常数 c > 1，使得 f(x) = O(cx)，那么函数 f(x) 就呈指数级增长（不会更快）。

对于 n⋅2ⁿ，常数 c 可以是大于 2 的任何数字，让我们取 3。然后： n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿ，对于任何 n 都小于 1。

因此，2ⁿ 的增长速度比 n⋅2ⁿ 更慢，后者的增长速度又比 2.000001ⁿ 更慢。但它们三个都呈指数级增长。

- Andrey

---

在最后一个例子中，n*2^n大于2.000001^n，直到n = 34,726,000。此时，2^n是一个具有超过1000万位数字的数字，所以这并不重要... - gnasher729

@gnasher729 这只是一个常数，我们可以省略为 f(n)，而 cf(n) 在大O符号的复杂度方面是相同的。例如，40'000'0002.000001^n 比 n*2^n 更大。但你是对的，这并不重要，我想说一旦我们达到指数增长，这就不重要了（除非我们只得到很小的 n 值）。 - Andrey

Answer 5

你问道“第二个问题和第一个问题的顺序一样吗？额外的n次方有影响吗？”这是两个不同的问题，有着不同的答案。

n 2^n 的增长速度大于 2^n 。这就回答了第一个问题。

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

在两种情况下，可以解决的最大问题规模在时间T内的复杂度都是 O(ln T)。

- gnasher729

Answer 6

非常简单的答案是“不”。

看到 2^n 和 n.2^n 如所见，对于任何 n>0，n.2^n > 2^n 或者你甚至可以在两边应用对数，然后你会得到

 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)

- user16133908