給定一個大小為 N 的陣列 A，對于每個元素 A[i]，我想找到所有滿足 A[j] > A[i] 的 j。目前，我想不出比 O(i) 更好的方法（遍歷所有 0 <= j < i 并檢查）。是否有一種演算法可以實作比上述更好的時間復雜度？空間復雜度可以是 O(N)
更新 1
我們可以假設陣列有不同的元素
更新 2
讓我們考慮陣列 A = [4 6 7 1 2 3 5]。令 dom(i) = {j | 0 < j < i 使得 A[j] > A[i] }
- dom(0) = 空
- dom(1) = 空
- dom(2) = 空
- dom(3) = {0, 1, 2}
- dom(4) = {0, 1, 2}
- dom(5) = {0, 1, 2}
- dom(6) = {1, 2}
O(N) 的空間復雜度也意味著每次迭代 i
uj5u.com熱心網友回復：
無法實作較低的時間復雜度，例如，如果您的陣列都是降序的，那么所有串列的總長度都是二次的，因此如果您的任務是獲取串列，那么這將盡可能快。您的解決方案已經達到了這個 O(N^2)，所以它已經是最優的了。
不過，有更快的方法來計算與此相關的一些事情。例如，如果您實際上只是想獲得所有此類對的總數，則可以在 O(n ln n) 時間內完成，請參閱這篇文章。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424341.html