Gọi là một mảng có kích thước N. chúng ta gọi là một vài chỉ số (i,j) một "nghịch đảo" nếu i < j và A[i] > A[j]tính số lượng "nghịch đảo" trong một hoán vị
Tôi cần phải tìm một thuật toán mà nhận được một loạt các kích thước N (với con số duy nhất) và trả lại số phần tử nghịch đảo trong thời điểm O(n*log(n)).
Bạn có thể sử dụng thuật toán merge sort.
Trong vòng lặp của thuật toán hợp nhất, nửa trái và phải đều được sắp xếp tăng dần và chúng tôi muốn hợp nhất chúng thành một mảng được sắp xếp đơn. Lưu ý rằng tất cả các phần tử ở phía bên phải có chỉ mục cao hơn so với các phần tử ở phía bên trái.
Giả sử mảng [leftIndex]> mảng [rightIndex]. Điều này có nghĩa là tất cả các phần tử ở phần bên trái sau phần tử có chỉ mục leftIndex cũng lớn hơn giá trị hiện tại ở bên phải (vì bên trái được sắp xếp tăng dần). Vì vậy, phần tử hiện tại ở phía bên phải tạo ra các số liệu đảo ngược numberOfElementsInTheLeftSide - leftIndex + 1, vì vậy hãy thêm số này vào số đảo ngược toàn cầu của bạn.
Khi thuật toán kết thúc thực hiện bạn có câu trả lời và sắp xếp hợp nhất là O (n log n) trong trường hợp xấu nhất.
Có một bài báo được xuất bản trong SIAM năm 2010 bởi Cham và Patrascu có tên Counting Inversions, Offline Orthogonal Range Counting, and Related Problems cho phép thuật toán lấy thời gian O (n sqrt (log (n))). Đây là thuật toán được biết đến nhiều nhất, và cải thiện thuật toán O (n log (n)/log (log (n)) dài hạn. Từ trừu tượng:
Chúng tôi đưa ra một O (n sqrt (lg n)) -time thuật toán cho đếm số lượng các đảo trong một hoán vị trên các yếu tố n. này cải thiện một lâu trước ràng buộc của O (n lg n/lg n lg) rằng tiếp từ cấu trúc dữ liệu Dietz của [WADS'89], và trả lời một câu hỏi của Andersson và Petersson [SODA'95 ]. Như Kết quả của Dietz được biết là tối ưu đối với vấn đề xếp hạng động liên quan, kết quả của chúng tôi thể hiện sự cải thiện đáng kể trong các cài đặt ngoại tuyến.
Kỹ thuật mới của chúng tôi khá đơn giản: chúng tôi thực hiện "phân vùng dọc" của trie (giống như cây van Emde Boas), và sử dụng ý tưởng từ bộ nhớ ngoài. Tuy nhiên, kỹ thuật này tìm thấy nhiều ứng dụng: ví dụ, chúng ta có được
- trong d kích thước, một thuật toán để câu trả lời n ẩn trực giao loạt truy vấn đếm trong thời gian O (n lg d-2 + 1/d n);
- cải thiện thời gian xây dựng cho dữ liệu trực tuyến cấu trúc cho phạm vi trực giao đếm;
- thời gian cập nhật được cải thiện cho vấn đề về khoản tiền một phần;
- nhanh hơn Thuật toán RAM từ để tìm kiếm độ sâu tối đa trong bố cục hình chữ nhật được căn chỉnh trục và cho bài toán chọn độ dốc .
Như một phần thưởng, chúng tôi cũng cung cấp cho một (1 + ε) thuật toán -approximation đơn giản cho đảo đếm chạy trong thời gian tuyến tính, cải thiện trước O (n lg lg n) ràng buộc bởi Andersson và Petersson.
Tôi nghĩ rằng cách awesomest để làm điều này (và đó chỉ vì tôi yêu cấu trúc dữ liệu) là sử dụng binary indexed tree. Tâm trí bạn, nếu tất cả bạn cần là một giải pháp, sắp xếp hợp nhất sẽ làm việc chỉ là tốt (tôi chỉ nghĩ rằng khái niệm này hoàn toàn đá!). Ý tưởng cơ bản là: Xây dựng một cấu trúc dữ liệu cập nhật các giá trị trong O (log n) và trả lời truy vấn "Có bao nhiêu số nhỏ hơn x đã xảy ra trong mảng cho đến nay?" Với điều này, bạn có thể dễ dàng trả lời số lượng lớn hơn x, góp phần đảo ngược với x là số thứ hai trong cặp. Ví dụ: xem danh sách {3, 4, 1, 2}.
Khi xử lý 3, không có số khác cho đến thời điểm này, vì vậy nghịch đảo với 3 ở bên phải = 0 Khi xử lý 4, số lượng ít hơn 4 cho đến nay = 1, do đó số lượng lớn hơn (và do đó inversions) = 0 Bây giờ, khi xử lý 1, số lượng nhỏ hơn 1 = 0, số lượng lớn hơn = 2 này góp phần vào hai nghịch đảo (3,1) và (4,1). Cùng một logic áp dụng cho 2 mà tìm thấy 1 số ít hơn nó và do đó 2 lớn hơn nó.
Bây giờ, câu hỏi duy nhất là hiểu cách các cập nhật và truy vấn này xảy ra trong nhật ký n. Url được đề cập ở trên là một trong những hướng dẫn hay nhất mà tôi đã đọc về chủ đề này.
Đây là những MERGE gốc và MERGE-Sắp xếp các thuật toán từ Cormen, Leiserson, Rivest, Stein Giới thiệu về thuật toán:
MERGE(A,p,q,r)
1 n1 = q - p + 1
2 n2 = r - q
3 let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
4 for i = 1 to n1
5 L[i] = A[p + i - 1]
6 for j = 1 to n2
7 R[j] = A[q + j]
8 L[n1 + 1] = infinity
9 R[n2 + 1] = infinity
10 i = 1
11 j = 1
12 for k = p to r
13 if L[i] <= R[j]
14 A[k] = L[i]
15 i = i + 1
16 else A[k] = R[j]
17 j = j + 1
và
MERGE-SORT(A,p,r)
1 if p < r
2 q = floor((p + r)/2)
3 MERGE-SORT(A,p,q)
4 MERGE-SORT(A,q + 1,r)
5 MERGE(A,p,q,r)
tại dòng 8 và 9 trong MERGE vô cực là thẻ được gọi là sentinel, có giá trị như vậy mà tất cả các phần tử mảng nhỏ hơn sau đó nó. Để có được số đảo ngược, bạn có thể giới thiệu số lượt truy cập toàn cục, giả sử ninv được khởi tạo bằng 0 trước khi gọi MERGE-SORT và hơn để sửa đổi thuật toán MERGE bằng cách thêm một dòng vào câu lệnh khác sau dòng 16, chẳng hạn như
ninv += n1 - i
hơn sau khi MERGE-Sắp xếp xong ninv sẽ giữ số đảo
Rất tương tự: http://stackoverflow.com/questions/4552591/how-to-find-the-number-of- inversions-in-an-array. Sự khác biệt là điều này chỉ định mảng chứa một hoán vị, trái ngược với các giá trị tùy ý. –
Cũng liên quan: [Đếm đảo ngược trong một mảng] (http://stackoverflow.com/questions/337664/counting-inversions-in-an-array) – PengOne