[理工] 演算法問題

[a2889184 (a2889184)]

大家好：

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
推 FRAXIS: O(k lg k) 應該不太可能吧 O(k lg n)比較可能
→ FRAXIS: O(k lg (n/k)) 也是可能的..
→ FRAXIS: 我是假設 A 和 B 都排序了  如果沒排序 那應該是要
→ FRAXIS: O(n lg n)了
推 aa06697: q1是從1-n選出k個相異數
→ hugo0203: a跟b都有k個數吧
→ a2889184: 所以A、B都是1～n取k個數字嗎 這樣就會變得比較合理了，
→ a2889184: 但是這樣的話代表他B的編號部分有錯。想上網找該年的考
→ a2889184: 題確認一下都找不到...