作者jason21716 (阿鴻)
看板Prob_Solve
標題[問題] 陣列中的比自己小的數字
時間Mon Oct 31 14:00:08 2016
各位好，小弟有一個演算法的問題想請教各位大大
有一個陣列，內有若N個不相同且隨機排列的數字
如：2 8 6 1 9 10 13 0
我需要依照陣列順序把排在自己之後而且比自己小的數字印出來
像這樣：
2 1
2 0
8 6
8 1
8 0
6 1
6 0
9 0
10 0
13 0
我知道如果用迴圈一個一個檢查總是有結果的
但是演算法效率是O(n^2)
想請問各位有沒有比O(n^2)更快的做法??
我想了很久，但都沒有比較好的解法...
不好意思麻煩各位了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.113.124.157
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1477893613.A.FC7.html
1F：推 ddavid: 極端來講，我給你8 7 6 5 4 3 2 1，你光是印出答案就需要 10/31 14:35
2F：→ ddavid: O(n^2)，頂多係數可以給你最小化到1/2罷了 10/31 14:36
是呀...這一點讓人很頭疼...
那如果說今天在不要求順序的狀況下，有可能提升速度嗎...
3F：推 ddavid: 直接做O(n log n) sort並保留原始順序的link，期待印出步 10/31 14:50
4F：→ ddavid: 驟的次數期望值落在O(n log n)也許比較實在 10/31 14:52
5F：推 CaptainH: 考慮merge sort，在merge時加個一兩行就行了 10/31 15:01
mergeSort嗎...
可是mergeSort在merge時一次都只看左右兩邊各一個數字
如果今天左邊的陣列數字全都比右邊的大，那就會出問題了...
但這似乎也是個好主意...透過merge時將左右兩邊排好
我讓左邊的最大值開始掃描右邊的最小值，
左>右就輸出值對，左<右就換左遍次大的重來一遍
左邊全部掃完之後就把兩邊merge起來
可是演算法效率...
mergeSort本身效率是O(nlogn)，但因為要掃描左右兩邊的大小
勢必得再加上這個步驟的成本...
剛剛拿大師定理算了一下，最糟糕的狀況(已經由大排到小)是O(n^2)
最好的狀況(由小到大)是O(nlogn)，平均狀況的話我在算算看
不過似乎是可行的做法....
....
不行，平均狀況的結果算來算去應該也會是O(n^2)
還需要更快的方法才行
6F：→ pttworld: 類別二欄位index和value，排序後判斷索引輸出得解。 10/31 16:29
是像這樣嗎?
原陣列 2 8 6 1 9 10 13 0
索引 0 1 2 3 4 5 6 7
排序後
value 0 1 2 6 8 9 10 13
index 7 3 0 2 1 4 5 6
然後從13開始，往前找index比它還大的數字嗎?
可是這樣子的效率還是O(n^2)....
或許是我誤解大大的意思了??
※ 編輯: jason21716 (120.113.124.157), 10/31/2016 17:40:14
7F：推 s89162504: mergesort怎會變成O(n^2) 10/31 19:52
8F：→ pttworld: 回原po，n個都要列出關係起算就n往上了。一樓說得很白。 10/31 20:05
9F：推 c225: 解的大小本來就Ω(n^2)了 所以merge sort複雜度應該是 11/01 00:20
10F：→ c225: O(nlogn + k) k是解大小~ 11/01 00:21
11F：推 DJWS: 比較快的方法應該是hashing/counting sort/位元操作之類的 11/01 10:38
12F：→ DJWS: 如果只能兩兩比較的話，那麼就是推文一樓說的那樣子，接下來 11/01 10:39
13F：→ DJWS: 的方向會是隨機算法/平滑分析之類的 11/01 10:39
14F：→ DJWS: 另外這題有個有趣的性質：當數值（連帶索引值）重新排序之後 11/01 10:41
15F：→ DJWS: 問題變成找到後方的更大索引值，類似於原本問題，但是索引值 11/01 10:42
16F：→ DJWS: 的範圍會是連續正整數，成為更簡單一點的問題 11/01 10:43
17F：→ DJWS: 至於這性質有什麼用...我也不知道 XD 11/01 10:43
18F：→ rifiz: count inversion problem? 11/07 02:24
19F：推 Astar5566: 沒錯 只是要印出來 11/07 16:28
20F：推 HoloLens: 看起來超像逆序數對，merge nlogn不會漏判啊 11/28 23:23
21F：→ HoloLens: 為何要掃左右兩邊？ 11/28 23:24