close

(最糟糕的下界?)<<亂翻譯

 

最好的sort可以把資料變成一棵樹

而資料量是n!

所以要做log(n!) 次

方法有兩種

 

第一種是用積分

log (n!)

= log ( n*(n-1)*(n-2)*...*2*1 )

=sigma(i=1~n) logi

(接下來就交給積分了...)

 

第二種是近似值

擷取  

log(n!)=

擷取  

(右邊括號內是常數)

所以Ω(nlogn)

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 cc08310112tw 的頭像
    cc08310112tw

    墨墨喵喵喵

    cc08310112tw 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄