I have to find the big-O Notation of the following expression:
2n + n(logn)10 + (1/2)n
If I ignore the coefficients, I get 2n + n (log n)10 plus some term involving 1/2. If I ignore the coefficients, I completely lose the last term, but it doesn't seem right to include them.
How should I handle the (1/2)n term?
对于 large n，接近 0 并且变得可以忽略不计。此外，与 相比，最终变得可以忽略不计，因为后者增长得更快。(1/2)n2nn(logn)10
比较等同于比较（因为两者都包含一个因子）。显然，将超过足够大的 s——实际上只需要一个of 。随着进一步增长，这两个术语之间的差异也会增加，并且该术语的意义将越来越小。n(logn)102n(logn)102n(logn)102nn3n2n
因此，我们剩下的大 O 表达式是
O(n(logn) 10 )
想想当 n 变大时 (1/2) n会发生什么。这个术语变得越来越小，最终变得完全可以忽略不计。（事实上，如果你选择 n = 30，它小于 1 / 1,000,000,000。）一个有用的观察是 (1/2) n ) 永远不会大于 1/2，所以你可以注意到
2n + n(log n) 10 + (1/2) n ≤ 2n + n(log n) 10 + 1/2
从那里，您可以看到这是 O(n (log n) 10 )，因为 n (log n) 10项比 2n 项增长得更快。
但是，通常情况下，您必须小心指数。a > 1的任何形式的n都将比任何多项式增长得更快，因此通常您会放弃多项式并保留指数。在这里，你做相反的事情。
希望这可以帮助！