理工

看板Grad-ProbAsk作者 (oldguy)時間7年前 (2018/08/21 11:12), 編輯推噓2(2推 0噓 3→)
留言5則, 2人參與, 7年前最新討論串1/2 (看更多)
https://i.imgur.com/gRqhTHR.jpg
第8.9題要怎麼判斷在worst時是否為linear time? 謝謝各位 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.50.145.161 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1534821133.A.73E.html
推
08/21 15:04, 7年前 , 1F
(8)comparison based的排序的lower bound是nlogn，可
08/21 15:04, 1F
→
08/21 15:05, 7年前 , 2F
以用decision tree證出來，所以worst case一定不可
08/21 15:05, 2F
→
08/21 15:05, 7年前 , 3F
能是linear time
08/21 15:05, 3F
推
08/21 15:08, 7年前 , 4F
(9)有一個selection algorithm它的worst case是O(n)
08/21 15:08, 4F
→
08/22 17:26, 7年前 , 5F
感謝樓上大神 我再重看一次筆記有比較懂了
08/22 17:26, 5F
‣ 更多 qazws3483 的文章
文章代碼(AID): #1RUuCDS- (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
4
12
理工 理工
qazws3483
7年前, 08/22
2
5
理工 理工
qazws3483
7年前, 08/21
在新視窗開啟完整討論串 (共2篇)
‣ 更多 qazws3483 的文章
文章代碼(AID): #1RUuCDS- (Grad-ProbAsk)