2 ^ n和n * 2 ^ n是否具有相同的时间复杂度？
我发现的关于时间复杂性的资源并不清楚什么时候可以忽略时间复杂性方程中的项，特别是使用非多项式的例子。
我很清楚，给定n2 + n + 1的形式，最后两个术语是微不足道的。
具体来说，给出两个分类，2n和n *（2n），是第二个与第一个相同的顺序？ 那里增加的n次乘法是否重要？ 通常资源只是说xn处于指数增长速度更快......然后继续前进。
我可以理解为什么它不会因为2n会大大超出n，而是因为它们没有被加在一起，所以在比较两个方程时它会很重要，实际上它们之间的差异总是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 2 m = 2ⁿ n⋅2ⁿ = ( log₂m )⋅m （取m = 2ⁿ两边的基数为2的对数给出n = log₂m m = 2ⁿ ），你可以很容易地表明m log₂m比m快。
我同意n⋅2ⁿ不在O(2ⁿ) ，但我认为它应该更明确一些，因为限制优先使用并不总是成立。
通过大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ⁿ增长得慢。
上一篇: Are 2^n and n*2^n in the same time complexity?
下一篇: Differences between time complexity and space complexity?