GiB*_* 09 0 algorithm math big-o
我必须找到以下表达式的big-O表示法:
2n + n(logn)10 +(1/2)n
如果我忽略系数,我得到2n + n(log n)10加上一些涉及1/2的项.如果我忽略系数,我完全失去了最后一个术语,但包含它们似乎并不正确.
我应该如何处理(1/2)n项？
对于大的n,接近0并且变得可以忽略不计.而且,与后者相比,最终变得可以忽略不计,因为后者增长得更快.(1/2)n2nn(logn)10
相比于等价于比较来(因为都包含的一个因素).显然,将超过足够大的S -实际上所有它需要的是的.随着进一步增长,这两个术语之间的差异也将增加,并且该术语的重要性将变得越来越小.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)ñ ≤2N + N(log n)的10 + 1/2
从那里,您可以看到这是O(n(log n)10),因为n(log n)10项比2n项增长得更快.
但是,通常情况下,你必须小心使用指数.a> 1的任何形式的n都会比任何多项式都快,所以通常你会丢弃多项式并保持指数.在这里,你做相反的事情.
希望这可以帮助!