找到函数的大O.

Question

请帮我完成以下两个功能,我需要简化它们.

O(nlogn + n ^ 1.01)

O(log(n ^ 2))

我目前的想法是

O(nlogn + n ^ 1.01)= O(nlogn)

O(log(n ^ 2))= O(log(n ^ 2))

请帮助我解决这两个简化问题并简要说明一下,谢谢.

Answer 1

对于第二个,你有O(lg(n²))= O(2lg(n))= O(lg(n)).

对于第一个,你有O(nlg(n)+ n ^(1.01))= O(n(lg(n)+ n ^(0.01)),你要决定lg(n)或n ^( 0.01)变大.

为此目的,你可以得到n ^ 0.01 - lg(n)的导数,看看在n - >无穷大的极限,它是正还是负:0.01/x ^(0.99) - 1/x; 在极限处,x大于x ^ 0.99,因此差异为正,因此n ^ 0.01渐近地增长比log(n)快,因此复杂度为O(n ^ 1.01).

Answer 2

记得:

log (x * y) = log x + log y

并且n^k总是比log n任何人都快k>0.