[理工] DS 101交大

看板Grad-ProbAsk作者 (KerKer)時間11年前 (2013/01/15 17:04), 編輯推噓0(006)
留言6則, 2人參與, 最新討論串1/1
Sorting 6 elements with a comparison sort require at least how many comparisons in the worst case? 答案是10 但我用HEAPSORT 算完是六次 還是他連建樹的比較也有考慮進去 但如果考慮進去好像就破表了 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.121.140.145

01/15 17:27, , 1F
事實上你把這六個元素建立決策樹 會發現外部節點有6!個
01/15 17:27, 1F

01/15 17:28, , 2F
內部節點6!-1個 整棵樹有2*6!-1個節點
01/15 17:28, 2F

01/15 17:28, , 3F
所以這個樹高就是lg (2*6!-1)
01/15 17:28, 3F

01/15 17:29, , 4F
也就是要比較這麼多次
01/15 17:29, 4F

01/15 19:59, , 5F
哦 好像是我算錯了 我忘記左右子點也要比較了
01/15 19:59, 5F

01/15 19:59, , 6F
謝謝
01/15 19:59, 6F
文章代碼(AID): #1GzHkJAX (Grad-ProbAsk)