2 ^ n和n * 2 ^ n在相同的时间复杂度？
我在时间复杂性上find的资源并不清楚什么时候可以忽略时间复杂度方程中的项，特别是非多项式的例子。
我很清楚，给定n 2 + n + 1的forms，后两项是不重要的。
具体来说，给出两个分类，2 n和n *（2 n ）是第二个与第一个相同的顺序？ 那么附加的n乘法是否重要？ 通常资源只是说x n处于指数增长速度更快，然后继续前进。
我可以理解为什么它不会因为n会大大超出n，而是因为它们没有被加在一起，所以在比较两个方程的时候会有很大的关系，实际上它们之间的差别总是n的一个因子，这至less可以说是很重要的。
为了回答这个问题，你必须去大O（ O ）的正式定义。
其定义是：当且仅当极限limsup x → ∞ (f(x)/g(x))存在，即limsup x → ∞ (f(x)/g(x))不属于无限。 简言之，这意味着存在一个常数M ，使得f(x)/g(x)值永远不会大于M
在你的问题的情况下，设f(n) = n ⋅ 2 n ，令g(n) = 2 n 。 那么f(n)/g(n)就是n ，它仍然会无限增长。 因此f(n)不属于O(g(n)) 。
看到n⋅2ⁿ更大的一个快速方法是改变variables。 令m = 2ⁿ 。 那么n⋅2ⁿ = ( log₂m )⋅m （取m = 2ⁿ两边的基数为2的对数给出n = log₂m m = 2ⁿ ），可以很容易地表明m log₂m比m快。
我同意n⋅2ⁿ不在O(2ⁿ) ，但是我认为它应该更明确，因为限制优先使用并不总是成立。
根据Big-O的forms定义：如果存在常数c > 0且n₀ ≥ 0 f(n) ≤ c⋅g(n) ，则对于所有f(n) ≤ c⋅g(n) c > 0 ， f(n)都在O(g(n)) f(n) ≤ c⋅g(n) 。 很容易certificatef(n) = n⋅2ⁿ且g(n) = 2ⁿ不存在这样的常数。 然而，可以certificateg(n)在O(f(n)) 。
换句话说， n⋅2ⁿ是更低的2ⁿ n⋅2ⁿ 这很直观。 虽然它们都是指数型的，因此在大多数实际情况下都不太可能被使用，但是我们不能说它们的顺序是相同的，因为2ⁿ必然比n⋅2ⁿ增长得慢。
我不争论与其他答案，说n⋅2ⁿ增长快于2ⁿ 。 但n⋅2ⁿ增长仍然只是指数。
当我们谈论algorithm时，我们经常说时间复杂度增长是指数的。 所以，我们认为是2ⁿ ， 3ⁿ ， eⁿ ， 2.000001ⁿ ，或者我们的n⋅2ⁿ是指数增长的同一组复杂度。
为了给它一点math意义，如果存在这样的常数c > 1 ，那么我们考虑一个函数f(x)以指数规律增长（不快），即f(x) = O(c x ) 。
对于n· n⋅2ⁿ ，常数c可以是任何大于2 ，我们取3 。 然后：
n⋅2ⁿ / 3ⁿ = n ⋅ (2/3)ⁿ对任何n都小于1 。
所以2ⁿ比n⋅2ⁿ 2ⁿ慢，最后又比2.000001ⁿ ？慢。 但是他们三人都成倍增长。
你问：“第一个和第一个是同一个顺序吗？附加的n次乘法是否重要？” 这是两个不同的问题，有两个不同的答案。
n 2 ^ n渐近地快于2 ^ n。 那就是这个问题的答案。
但是你可以问：“如果algorithmA需要2 ^ n纳秒，algorithmB需要2 ^ n纳秒，那么我可以在第二/分钟/小时/天/月/年find解决scheme的最大n是多less？答案是n = 29/35/41/46/51/54与25/30/36/40/45/49。实践没有太大的区别。
可以在时间T内解决的最大问题的大小在两种情况下都是O（ln T）。
