math - 我的 Big Oh 有问题

Question

你好试图解决我的大哦，但我不确定什么是对的。我的功能是：

F(n)=((n+1)logn+log(n+3)-(n+1)+2)/n

我锻炼：

(log(n^(n+1))+log(n+3)-n+1)/n

(log((n^n)*n)+log(n+3)-n+1)/n

(log(n^n)+logn+log(n+3)-n+1)/n

(nlogn+logn+log(n+3)-n+1)/n

logn +(logn)/n+(log(n+3))/n-1+1/n

我可以算出 log(n+3) -> logn。但我不确定的部分是（logn）/n 的 Big-Oh 是什么。是等于nlogn还是logn。

我目前的遮阳篷是：

F(n)= logn +(logn)/n+(log(n+3))/n-1+1/n

logn +(logn)/n+(log(n+3))/n-1+1/n <= (1+1+1+1+1) nlogn     where c=5 & n0=2

谢谢

Answer 1

对于每一个c > 0，你可以找到一个n0这样的

\forall n > n0, log( n ) / n < c*log( n )

所以

log(n)/n \in o( log(n) ) (little-oh).  

实际上，

log(n)/n \in o( 1 ) 

所以，

log(n) + log(n)/n + log(n+3)/n - 1 + 1/n \in  \Theta( log(n) )