我在时间复杂度上找到的资源不清楚什么时候可以忽略时间复杂度方程中的项，特别是对于非多项式示例。
我很清楚，给定 n2 + n + 1 形式的东西，最后两项是微不足道的。
具体来说，给定两个分类，2n 和 n*(2n)，第二个与第一个的顺序相同吗？额外的 n 乘法有关系吗？通常资源只是说 xn 呈指数增长并且增长得更快......然后继续前进。
我可以理解为什么它不会，因为 2n 将大大超过 n，但是因为它们没有被加在一起，所以在比较两个方程时会非常重要，实际上它们之间的差异将始终是 n 的一个因数，即至少可以这么说似乎很重要。
最佳答案
您将必须转到大 O ( O ) 的正式定义才能回答此问题。
定义是 f(x) 属于 O(g(x)) 当且仅当极限 limsup (f(x)/g(x)) 存在即不是无穷大。简而言之，这意味着存在一个常量 M ，因此 f(x)/g(x) 的值永远不会大于 M 。
在你的问题的情况下，让 f(n) = n ⋅ 2 和让 g(n) = 2。那么 f(n)/g(n) 是 n ，它仍然会无限增长。因此 f(n) 不属于 O(g(n)) 。
关于algorithm - 2^n 和 n*2^n 的时间复杂度相同吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21764861/