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

我在时间复杂性方面发现的资源并不清楚什么时候可以忽略时间复杂性方程中的项，特别是在非多项式的例子中。

对我来说，很明显，如果是 n2 + n + 1的形式，那么最后两项就是无关紧要的。

具体地说，给定两个分类2N和 n * (2N) ，第二个分类是否与第一个分类的顺序相同？这里附加的 n 乘法重要吗？通常资源只是说 xN是指数级的，并且增长得更快... 然后继续。

我可以理解为什么它不会，因为2N会大大超过 n，但是因为它们没有被加在一起，所以在比较两个方程时会很重要，事实上它们之间的差总是 n 的因子，这至少看起来很重要。

35998 次浏览
小开

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

小开
最佳答案

为了回答这个问题，你必须去寻找大 O (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))。

小开

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

根据 Big-O 的形式定义: 如果存在常数 c > 0和 n₀ ≥ 0，那么对于所有的 n ≥ n₀，我们都有 f(n) ≤ c⋅g(n)，那么 f(n)在 O(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，这都小于 1。

所以 2ⁿ的生长速度比 n⋅2ⁿ慢，而 n⋅2ⁿ的生长速度又比 2.000001ⁿ慢。但它们都呈指数级增长。

小开

你问“第二个和第一个的顺序是一样的吗?”？加上 n 的乘法有关系吗?”这是两个不同的问题，有两个不同的答案。

N 2 ^ n 渐近地比2 ^ n 增长得快，这就是问题的答案。

但是你可以问“如果算法 A 需要2 ^ n 纳秒，而算法 B 需要 n 2 ^ n 纳秒，那么在1秒/分钟/小时/天/月/年中我能找到的最大 n 是多少?”？答案是 n = 29/35/41/46/51/54比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)

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

  1. 替换一个数字

  2. 用木头

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

所以如果你得到一个方程

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


提交答案