Cần giúp bài tập về độ phức tạp thuật toán

Dùng tư tưởng chia để trị giống như merge sort:

• Chia mảng a thành 2 phần left, right:
• Đếm cặp nghịch đảo trong mỗi phần
• Đếm cặp nghịch đảo khi trộn hai mảng left và right

bước quan trọng nhất ở đây là phần trộn hai mảng left và right, khi trộn số cặp nghịch đảo có được chính là tổng số các số bé hơn của mảng right so với mảng left hay = sum count(right[j]<left[i]) (1)
Vì các bước này tương tự merge sort nên chỉ cần thêm bước đếm biểu thức (1) khi mà right[j] <left[i] trong bước trộn của sắp xếp trộn. Khi mà dãy left,right đã được sắp xếp thì việc (1) = sum(len(left)-i) chính là việc đếm số lớn hơn right[j] trong dãy left đó cũng chính là kết quả bài toán

Code tham khảo:

def count(a):
    n=len(a)
    if n<2:
        return 0
    left=a[:n//2]
    right=a[n//2:]
    ans=0
    ans+=count(left)
    ans+=count(right)

    i=0
    j=0
    k=0
    while i<len(left) and j<len(right):
        if left[i]<=right[j]:
            a[k]=left[i]
            i+=1
            k+=1
        else:
            a[k]=right[j]
            j+=1
            k+=1
            ans+=len(left)-i
    if i<len(left):
        a[k:]=left[i:]
    if j<len(right):
        a[k:]=right[j:]
    return ans

print count([2,3,8,6,1])

hehe bài này giống y như bài đếm số lượng swap trong insertion sort

Ngoài cach dùng Merge Sort ra thì cũng còn 1 cách nữa

• Cùng độ phức tạp (NlogN)
• Chạy nhanh hơn
• Code gọn hơn
• Não chết nhanh hơn :)))
  Đó là dùng Fenwick Tree a.k.a Binary Indexed Tree, đây là một bài là ứng dụng cơ bản và áp dụng code BIT thuần túy vào luôn, nên nếu bạn đã học BIT rồi chắc chắn sẽ không cần phải hỏi, và ngược lại đã hỏi thì chưa biết, mình chỉ reply để nếu ai muốn tìm hiểu thêm thì có thể coi thử nó là cái gì. Chứ như đã nói, đọ hack não của nó là ghê hơn rất nhiều so với Merge nên nếu chưa biết thì dùng Merge an toàn hơn.

đây là lệnh gì anh. Em chưa rành Python lắm:
left=a[:n//2]
right=a[n//2:]

chạy thử: https://www.hackerrank.com/challenges/insertion-sort

giải thích cách vừa merge vừa đếm số lượng swap: https://www.cs.colostate.edu/~cs320/Slides/05_inv.pdf