2n和n*2n的时间复杂度是一样的吗？

提问者：小点点

我找到的关于时间复杂度的资料不清楚何时可以忽略时间复杂度方程中的项，特别是非多项式的例子。

对于我来说，很清楚，如果给出nsup2/sup>+n+1的形式，最后两个术语是不重要的。

具体地说，给定两个分类，2supn/sup>和N*(2supn/sup)，第二个分类是否与第一个分类的顺序相同？那附加的n乘法有关系吗？通常，资源只是说xsupn/sup>呈指数增长，并且增长得更快。那就继续吧。

我可以理解为什么它不会，因为2supn/sup>会大大超过n，但是因为它们不是相加的，所以在比较这两个方程时，这会很重要，事实上，它们之间的差永远是n的因子，至少这看起来很重要。

共3个答案

匿名用户

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

定义是属于当且仅当极限(f(x)/g(x))/code>存在，即不是无穷大。简而言之，这意味着存在一个常量，使得的值永远不会大于。

在您的问题中，让和。那么就是仍将无限增长的。因此不属于。

匿名用户

查看是否更大的一个快速方法是更改变量。设。然后（在两边取以2为底的对数得到)，您可以很容易地显示比增长得更快。

匿名用户

我同意不在中，但我认为它应该更加明确，因为superior用法的限制并不总是有效的。

根据big-o的形式化定义:在中，如果存在常量；0/code>和，使得对于所有，我们具有。对于和，可以很容易地证明不存在这样的常量。但是，可以显示在中。

换句话说，的下界为。这是直观的。虽然它们都是指数型的，因此在大多数实际情况下都不太可能使用，但我们不能说它们是相同的顺序，因为的增长速度必然比慢。