2007-12-23

取log法比大小

n^lg3和nlgn比

兩邊同取lg=>lg(n^lg3) lg(nlgn)

把lg3搬下來=>lg3lgn lg(nlgn)

lg3看成常數c=> clgn lg(nlgn)

結果 lg(nlgn) 比 clgn 大 所以n^lg3=O(nlgn)

但是答案是nlgn=O(n^lg3)

請問這樣看哪裡錯了呢??
於

5 則留言:

  1. nimigo2007年12月24日 下午1:50

    如果把lg(nlgn)看成lgn+lglgn;
    clgn看成lgn+lgn+lgn+...+lgn(加c次)
    那clgn應該就比較大了喔@@a

    回覆刪除
  2. Joshua2007年12月24日 晚上11:50

    我覺得這兩個函數是不能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)

    回覆刪除
  3. CY2007年12月24日 晚上11:59

    作者已經移除這則留言。

    回覆刪除
  4. CY2007年12月25日 凌晨12:01

    同上
    也可以用lim來比較
    lim(n^lg3/nlgn)=
    lim(n^(lg3-1)/lgn)=無限大
    所以nlgn=O(n^lg3)

    回覆刪除
  5. 亞森2007年12月25日 中午12:30

    觀察法 clgn 與 lg(nlgn)
    c最多也只到n,所以nlgn
    ,而lg(nlgn)頂多也只有對數order,在n0 >= 2

    lim法也可以

    所以答案是nlgn=O(n^lg3)

    回覆刪除