各位好，小弟有一個演算法的問題想請教各位大大
有一個陣列，內有若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)更快的做法??
我想了很久，但都沒有比較好的解法...
不好意思麻煩各位了
作者:
ddavid (謊言接線生)
2016-10-31 14:35:00極端來講，我給你8 7 6 5 4 3 2 1，你光是印出答案就需要O(n^2)，頂多係數可以給你最小化到1/2罷了直接做O(n log n) sort並保留原始順序的link，期待印出步驟的次數期望值落在O(n log n)也許比較實在
作者:
CaptainH (Cannon)
2016-10-31 15:01:00考慮merge sort，在merge時加個一兩行就行了
作者:
pttworld (批踢踢世界)
2016-10-31 16:29:00類別二欄位index和value，排序後判斷索引輸出得解。
作者:
pttworld (批踢踢世界)
2016-10-31 20:05:00回原po，n個都要列出關係起算就n往上了。一樓說得很白。
作者: c225 (嘟嘟嚕~~~) 2016-11-01 00:20:00
解的大小本來就Ω(n^2)了 所以merge sort複雜度應該是O(nlogn + k) k是解大小~
作者:
DJWS (...)
2016-11-01 10:38:00比較快的方法應該是hashing/counting sort/位元操作之類的如果只能兩兩比較的話，那麼就是推文一樓說的那樣子，接下來的方向會是隨機算法/平滑分析之類的另外這題有個有趣的性質：當數值（連帶索引值）重新排序之後問題變成找到後方的更大索引值，類似於原本問題，但是索引值的範圍會是連續正整數，成為更簡單一點的問題至於這性質有什麼用...我也不知道 XD
作者:
rifiz (薩哈拉雅)
2016-11-07 02:24:00count inversion problem?
作者:
HoloLens (GoogleGlass沒了ww)
2016-11-28 23:23:00看起來超像逆序數對，merge nlogn不會漏判啊為何要掃左右兩邊？