推 P568912:謝謝原PO 我好像自己有想通一點!!! 10/31 05:07
bubble sort tree 的leaves會剛剛好有n!個
因為n個數字排列順序可能會有n!種
所有node的數目也跟n!有關
而這個樹的深度大略是log(n!)這麼深
log(n!) <= log(n^n)
<= n*log(n)
所以每個結果走到底要花n*log(n)的時間
這只是比較不嚴謹的講法
抱歉那天下課太匆促沒有講清楚
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.180.185