[演算] 給謝宗廷 bubble sort tree

看板NTUBIME100HW作者 (阿華田)時間16年前 (2009/10/24 11:54), 編輯推噓1(1推 0噓 0→)
留言1則, 1人參與, 最新討論串1/1
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
推
10/31 05:07, , 1F
謝謝原PO 我好像自己有想通一點!!!
10/31 05:07, 1F
‣ 更多 ajnightmare 的文章
文章代碼(AID): #1Audg8ci (NTUBIME100HW)