※ 引述《poc7667 (poc)》之銘言： : 在2n大小的陣列中，挑出n個元素排成陣列。 : 而這n個元素所形成的陣列，第i個元素，是原本的整個陣列第2i個大 : 比如說原本陣列A[2N] <-unsorted : 而我們選出的陣列叫做B[N] : B[6]這個元素就是原本整個陣列的第12大。 : 目前我只想到用quick sort下去解，但是time complexity只能到 NlogN : 請問有更快的解法嗎？ : 這不是作業，只是考古題的題目，最近應付考試:) : 謝謝 假設對這個問題我們有 O(N) 的解法。 顯然將 第2i大 改成 第2i小 不會改變時間複雜度 這時 對 A 做一次"第2i大"的問題 得到結果 B 對 A 做一次"第2i小"的問題 得到結果 C 那麼 由於A的大小是偶數 故 B 和 C 兩者恰好形成 A 的一個分割 因此將 B 和 C 做 Merge-sort 的合併步驟即可得到 A 的排序結果 如果假設成立 那以上演算法將會在 O(N) 時間內把 A 排好 因此若限定排序為比較型排序的話 則產生矛盾 (比較型排序的 time complexity 底限為 O(NlogN)) 若不限定的話 利用 O(N) 的(限定情形下的)排序 (例如radix-sort) 原問題的確存在 O(N) 的做法 (也就是排好再抓出來就是了XD) -- 像這種和排序有關的問題 基本想法就是去證不用排序不會比較好 也就是說 如果真的有比較好的答案 那用它可以反過來打破排序已知的結論 (就像上面的做法一樣) -- 是說這篇貌似比較適合 Prob_Solve 版...XD -- "LPH" is for "Let Program Heal us".... --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.84 ※ 編輯: LPH66 來自: 140.112.30.84 (02/25 19:00)