Phần tử đứng trước lớn hơn phần tử đứng sau
Một cặp chỉ số (i,j) là nghịch đảo khi **i<j và A[i]>A[j]**. Chỉ số tính từ 0; hai giá trị bằng nhau không tạo nghịch đảo.
Với A=[6,2,6,1], có các cặp:
| Chỉ số gốc (i,j) | Giá trị (A[i],A[j]) |
|---|---|
| (0,1) | (6,2) |
| (0,3) | (6,1) |
| (1,3) | (2,1) |
| (2,3) | (6,1) |
Có 4 cặp. Hai dòng có cùng giá trị (6,1) vẫn là hai cặp khác nhau vì số 6 ở hai vị trí khác nhau. Cặp (0,2) không được tính vì hai giá trị đều bằng 6.
Mỗi i chỉ so với các j đứng sau
```python
def count_simple(A):
count = 0
for i in range(len(A) - 1):
for j in range(i + 1, len(A)):
if A[i] > A[j]:
count += 1
return count
```
Vòng trong bắt đầu tại i+1, nên không so một vị trí với chính nó và không xét lại cặp theo chiều ngược. Có n(n−1)/2 cặp chỉ số cần so sánh, vì vậy bậc thời gian là O(n²). Dãy rỗng hoặc một phần tử trả 0.
Dãy không giảm có 0 nghịch đảo; dãy giảm thực sự có n(n−1)/2 nghịch đảo. Nếu có giá trị trùng, không kết luận mọi cặp đều nghịch đảo chỉ từ việc dãy không tăng.
Bài luyện
Trong A=[6,2,6,1], vì sao (0,2) không là cặp nghịch đảo?
0<2 đúng; thiếu điều kiện giá trị.
Bài đang dùng chỉ số từ 0.
Các cặp (0,1),(0,3),(2,3) vẫn hợp lệ.
Điều kiện giá trị là >, không phải >=.
Lời giải
Cặp có 0<2 nhưng A[0]=A[2]. Nghịch đảo cần đồng thời i<j và A[i]>A[j], nên cặp này không được tính.
Bài luyện
Dãy mẫu có hai cặp giá trị (6,1). Cần đếm thế nào?
Bài toán đếm cặp vị trí thỏa điều kiện.
Gộp sẽ mất một cặp chỉ số hợp lệ.
Các giá trị của mỗi cặp vẫn có 6>1.
Chiều ngược không thỏa i<j.
Lời giải
Hai số 6 ở chỉ số 0 và 2 đều đứng trước số 1 ở chỉ số 3. Vì vậy có hai nghịch đảo khác nhau dù biểu diễn bằng giá trị trùng nhau.
Bài luyện
Dãy [5,5] có bao nhiêu cặp nghịch đảo?
Không lấy mọi tổ hợp chỉ số kể cả trùng và ngược.
Hai giá trị bằng nhau, không thỏa >.
Cặp chỉ số (0,1) có tồn tại nhưng không là nghịch đảo.
Không đếm riêng hai phần tử thành hai cặp.
Lời giải
Chỉ có cặp chỉ số (0,1), nhưng5 không lớn hơn 5. Do đó số nghịch đảo bằng 0.
Đang học