Оптимальный код, чтобы найти количество пар с условием больше, чем в списке на основе индекса?

Question

Допустим, A = [5,2,1,3], обозначим количество пар (i, j). 1 <= i <j <= n такой, что A [i]> A [j]. Ниже приведен неоптимизированный код для того же

def I(A):
    output = i = j = 0
    while i< len(A):
        j = i+1
        while j<len(A):
            if A[i]>A[j]:
                output +=1
            j+=1
        i+=1
    return output

Answer 1

Похоже, ваша проблема в подсчете инверсий, очень известном в конкурентном программировании, оптимальным решением для этого является использование mergesort, вы можете найти множество реализаций в inte rnet, мне нравится в geeksforgeeks: https://www.geeksforgeeks.org/counting-inversions/

Основная идея c заключается в использовании принципа «разделяй и властвуй», в статье выше очень хорошо объясняется проблема.