[理工] 演算法 複雜度

看板Grad-ProbAsk作者 (bmpss92196)時間6年前 (2018/04/21 11:36), 6年前編輯推噓1(1推 0噓 8→)
留言9則, 2人參與, 6年前最新討論串2/2 (看更多)
想請教此題 The comparison-based sorting algorithm on n data requires Ω(nlgn) time. 我的理解 根據Ω的意思，此題應該是要證comparison-based sorting 至少(最好情況)nlgn的複雜度 而解答上寫在worst case時至少需要h(樹高)次的比較 再來n個數有n!種可能性的排序，每個葉存一個，至少要有n!個葉 h高度的葉最多為2^h個 我的問題是解答上先說是worst case，但題目不是要最好情況下嗎？ 如n=3，a,b,c三數比大小 最好情況不是a>b成立b>c成立 => a>b>c 這樣嗎？ 有點不太理解解答的意思，謝謝 另外再請教林立宇老師課本上證明lg(n!)=Θ(nlgn)跟有些題目都沒有取c 定義上是要取c，是可以省略還是必須寫？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.174.225.79 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1524281800.A.612.html ※ 編輯: bmpss92196 (1.174.225.79), 04/21/2018 12:00:58
→
04/21 12:48, 6年前 , 1F
我的理解，requires是考慮最壞情況需要的時間
04/21 12:48, 1F
→
04/21 12:49, 6年前 , 2F
加上Ω的意思是，最壞情況至少需要這樣的時間。
04/21 12:49, 2F
推
04/21 13:21, 6年前 , 3F
Ω不一定跟"best case"配對，如果和"worst case"搭配代表
04/21 13:21, 3F
→
04/21 13:21, 6年前 , 4F
我們想分析worst case下至少要多久時間
04/21 13:21, 4F
→
04/21 13:24, 6年前 , 5F
sorting去分析最好情況比較沒意義，因為最好的狀況可能是
04/21 13:24, 5F
→
04/21 13:24, 6年前 , 6F
已經排序好的數列，這個狀況底下很多sorting方法會是line
04/21 13:24, 6F
→
04/21 13:24, 6年前 , 7F
ar time
04/21 13:24, 7F
→
04/21 13:27, 6年前 , 8F
我沒有上林立宇的課，不過推測沒取的意思應該就是等於取c
04/21 13:27, 8F
→
04/21 13:27, 6年前 , 9F
=1
04/21 13:27, 9F
感謝兩位大大，懂了 ※ 編輯: bmpss92196 (1.174.225.79), 04/21/2018 14:34:27
‣ 更多 bmpss92196 的文章
文章代碼(AID): #1Qsh78OI (Grad-ProbAsk)
‣ 更多 bmpss92196 的文章
文章代碼(AID): #1Qsh78OI (Grad-ProbAsk)