Research Space for Linear Algebra & Discrete Mathematics
如果把lg(nlgn)看成lgn+lglgn;clgn看成lgn+lgn+lgn+...+lgn(加c次)那clgn應該就比較大了喔@@a
我覺得這兩個函數是不能log法來判別的..因為O(lg(n^lg3))=O(lg3lgn)=O(lgn)而O(lg(nlgn))=O(lgn+lglgn)=O(lgn)當結果是兩個函數的order一樣大時log法就沒效了我的想法是直接用看的.把lg3當作常數c來看則n^c的order是polynomial time等級=> nlgn=O(n^c)
同上也可以用lim來比較lim(n^lg3/nlgn)=lim(n^(lg3-1)/lgn)=無限大所以nlgn=O(n^lg3)
觀察法 clgn 與 lg(nlgn)c最多也只到n,所以nlgn,而lg(nlgn)頂多也只有對數order,在n0 >= 2lim法也可以所以答案是nlgn=O(n^lg3)
張貼留言
5 則留言:
如果把lg(nlgn)看成lgn+lglgn;
clgn看成lgn+lgn+lgn+...+lgn(加c次)
那clgn應該就比較大了喔@@a
我覺得這兩個函數是不能log法來判別的..
因為O(lg(n^lg3))=O(lg3lgn)=O(lgn)
而O(lg(nlgn))=O(lgn+lglgn)=O(lgn)
當結果是兩個函數的order一樣大時
log法就沒效了
我的想法是
直接用看的.
把lg3當作常數c來看
則n^c的order是polynomial time等級
=> nlgn=O(n^c)
同上
也可以用lim來比較
lim(n^lg3/nlgn)=
lim(n^(lg3-1)/lgn)=無限大
所以nlgn=O(n^lg3)
觀察法 clgn 與 lg(nlgn)
c最多也只到n,所以nlgn
,而lg(nlgn)頂多也只有對數order,在n0 >= 2
lim法也可以
所以答案是nlgn=O(n^lg3)
張貼留言