[理工] 演算法問題

看板Grad-ProbAsk作者 (a2889184)時間9年前 (2016/08/28 11:05), 編輯推噓2(2推 0噓 7→)
留言9則, 4人參與, 最新討論串1/4 (看更多)
大家好： http://i.imgur.com/x9wgbtw.jpg
http://i.imgur.com/QxyBAG5.jpg
有兩個問題想要請教一下： 1.題目第一行後半段的意思是什麼（of k <=n開使）...是指k是一個從｛1～n｝選出來的 數嗎。 2.他說要設計一個klogk的解法，可是他下面的解答在sort（B)這步複雜度應該是nlogn ，因為n>=k 所以應該超過klogk 了才是，還是其實n,k大小在複雜度計算是沒差的？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1472353515.A.B77.html
推
08/28 11:38, , 1F
O(k lg k) 應該不太可能吧 O(k lg n)比較可能
08/28 11:38, 1F
→
08/28 11:38, , 2F
O(k lg (n/k)) 也是可能的..
08/28 11:38, 2F
→
08/28 11:40, , 3F
我是假設 A 和 B 都排序了 如果沒排序 那應該是要
08/28 11:40, 3F
→
08/28 11:40, , 4F
O(n lg n)了
08/28 11:40, 4F
推
08/28 11:53, , 5F
q1是從1-n選出k個相異數
08/28 11:53, 5F
→
08/28 13:19, , 6F
a跟b都有k個數吧
08/28 13:19, 6F
→
08/28 14:06, , 7F
所以A、B都是1～n取k個數字嗎 這樣就會變得比較合理了，
08/28 14:06, 7F
→
08/28 14:06, , 8F
但是這樣的話代表他B的編號部分有錯。想上網找該年的考
08/28 14:06, 8F
→
08/28 14:06, , 9F
題確認一下都找不到...
08/28 14:06, 9F
‣ 更多 a2889184 的文章
文章代碼(AID): #1NmbJhjt (Grad-ProbAsk)
‣ 更多 a2889184 的文章
文章代碼(AID): #1NmbJhjt (Grad-ProbAsk)