[問題] 陣列中的比自己小的數字

[jason21716 (阿鴻)]

各位好，小弟有一個演算法的問題想請教各位大大

有一個陣列，內有若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://www.ptt.cc/bbs/Prob_Solve/M.1477893613.A.FC7.html
推 ddavid: 極端來講，我給你8 7 6 5 4 3 2 1，你光是印出答案就需要
→ ddavid: O(n^2)，頂多係數可以給你最小化到1/2罷了
是呀...這一點讓人很頭疼...
那如果說今天在不要求順序的狀況下，有可能提升速度嗎...
推 ddavid: 直接做O(n log n) sort並保留原始順序的link，期待印出步
→ ddavid: 驟的次數期望值落在O(n log n)也許比較實在
推 CaptainH: 考慮merge sort，在merge時加個一兩行就行了
mergeSort嗎...
可是mergeSort在merge時一次都只看左右兩邊各一個數字
如果今天左邊的陣列數字全都比右邊的大，那就會出問題了...

但這似乎也是個好主意...透過merge時將左右兩邊排好
我讓左邊的最大值開始掃描右邊的最小值，
左>右就輸出值對，左<右就換左遍次大的重來一遍
左邊全部掃完之後就把兩邊merge起來

可是演算法效率...
mergeSort本身效率是O(nlogn)，但因為要掃描左右兩邊的大小
勢必得再加上這個步驟的成本...
剛剛拿大師定理算了一下，最糟糕的狀況(已經由大排到小)是O(n^2)
最好的狀況(由小到大)是O(nlogn)，平均狀況的話我在算算看
不過似乎是可行的做法....

....
不行，平均狀況的結果算來算去應該也會是O(n^2)
還需要更快的方法才行
→ pttworld: 類別二欄位index和value，排序後判斷索引輸出得解。
是像這樣嗎?

原陣列 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
推 s89162504: mergesort怎會變成O(n^2)
→ pttworld: 回原po，n個都要列出關係起算就n往上了。一樓說得很白。
推 c225: 解的大小本來就Ω(n^2)了 所以merge sort複雜度應該是
→ c225: O(nlogn + k) k是解大小~
推 DJWS: 比較快的方法應該是hashing/counting sort/位元操作之類的
→ DJWS: 如果只能兩兩比較的話，那麼就是推文一樓說的那樣子，接下來
→ DJWS: 的方向會是隨機算法/平滑分析之類的
→ DJWS: 另外這題有個有趣的性質：當數值（連帶索引值）重新排序之後
→ DJWS: 問題變成找到後方的更大索引值，類似於原本問題，但是索引值
→ DJWS: 的範圍會是連續正整數，成為更簡單一點的問題
→ DJWS: 至於這性質有什麼用...我也不知道 XD
→ rifiz: count inversion problem?
推 Astar5566: 沒錯 只是要印出來
推 HoloLens: 看起來超像逆序數對，merge nlogn不會漏判啊
→ HoloLens: 為何要掃左右兩邊？