Делаем сложность меньше (лучше)

Одним из самых известных алгоритмов «разделяй и властвуй» является сортировка слиянием. И сортировка слиянием на самом деле является действительно хорошей основой для этого алгоритма.

Идея состоит в том, что при сравнении двух чисел из двух разных «разделов» у вас уже есть много информации об оставшейся части этих разделов, поскольку они сортируются на каждой итерации.

Возьмем пример!

Рассмотрим следующие разделы, которые уже были отсортированы по отдельности и подсчитаны «хорошие пары».

Раздел x: [1, 3, 6, 9].

Раздел y: [4, 5, 7, 8].

Важно отметить, что номера раздела x расположены левее в исходном списке, чем раздел y. В частности, для каждого элемента в x соответствующий индекс i должен быть меньше некоторого индекса j для каждого элемента в y.

Мы начнем со сравнения 1 и 4. Очевидно, что 1 меньше 4. Но поскольку 4 — наименьший элемент в разбиении y, 1 также должен быть меньше остальных элементов в y. Следовательно, мы можем заключить, что имеется 4 дополнительных хороших пары, так как индекс 1 также меньше, чем индекс остальных элементов y.

То же самое происходит с 3, и мы можем добавить к сумме 4 новые хорошие пары.

Для 6 сделаем вывод, что есть две новые хорошие пары. Сравнение между 6 и 4 не дало хорошей пары, как и для 6 и 5.

Теперь вы могли заметить, как будут подсчитываться эти дополнительные хорошие пары? В основном, если элемент из x меньше элемента из y, добавьте количество элементов, оставшихся в y, к сумме. Прополощите и повторите.

Поскольку сортировка слиянием — это алгоритм O(n log n), а дополнительная работа в этом алгоритме постоянна, мы можем заключить, что этот алгоритм также является алгоритмом O (n log n).

Я оставлю фактическое программирование в качестве упражнения для вас.

@niklasaa добавил объяснение аналогии с сортировкой слиянием, но в вашей реализации все еще есть проблема.

Вы разбиваете массив и вычисляете результат для любой половины, но

1. На самом деле вы не отсортировали ни одну из половин. Поэтому, когда вы сравниваете их элементы, ваш подход с двумя указателями неверен.
2. Вы не использовали их результаты в окончательных вычислениях. Вот почему вы получаете неправильный ответ.

Что касается пункта № 1, вам следует обратить внимание на сортировку слиянием, особенно на функцию merge(). Именно эта логика даст вам правильное количество пар без O(N^2) итерации.

Для точки № 2 сначала сохраните результат для любой половины:

# Sorting the first half
leftCount = goodPairs(left_side)
  
# Sorting the second half
rightCount = goodPairs(right_side)

Возвращая окончательный счет, добавьте и эти два результата.

return count + leftCount + rightCount

Как заявил @Abhinav Mathur, у вас есть большая часть кода, ваша проблема связана с этими строками:

# Sorting the first half
goodPairs(left_side)

# Sorting the second half
goodPairs(right_side)

Вы хотите сохранить их в переменных, которые должны быть объявлены перед оператором if. Вот обновленная версия вашего кода:

def goodPairs(arr):
    count = 0 
    left_count = 0
    right_count = 0

    if len(arr) > 1:
        mid = len(arr) // 2
  
        left_side = arr[:mid]
  
        right_side = arr[mid:]
  
        left_count = goodPairs(left_side)
  
        right_count = goodPairs(right_side)

        for i in left_side:
            for j in right_side:
                if i < j:
                    count += 1
    return count + left_count + right_count

Иногда рекурсия может быть сложной, изучите идею сортировки слиянием и быстрой сортировки, чтобы лучше понять, как работают алгоритмы «разделяй и властвуй».

Ранее принятый ответ Текущий от Fire Assassin на самом деле не отвечает на вопрос, который требует большей сложности. Оно по-прежнему квадратичное и примерно такое же быстрое, как гораздо более простое квадратичное решение. Сравнительный анализ с 2000 перемешанными целыми числами:

387.5 ms  original
108.3 ms  pythonic
104.6 ms  divide_and_conquer_quadratic
  4.1 ms  divide_and_conquer_nlogn
  4.6 ms  divide_and_conquer_nlogn_2

Код (Попробуйте онлайн!):

def original(nums):
    count = 0
    for i in range(0,len(nums)):
        for j in range(i+1,len(nums)):    
            if i < j and nums[i] < nums[j]:
                count += 1
                j += 1
            j += 1
    return count

def pythonic(nums):
    count = 0
    for i, a in enumerate(nums, 1):
        for b in nums[i:]:
            if a < b:
                count += 1
    return count

def divide_and_conquer_quadratic(arr):
    count = 0 
    left_count = 0
    right_count = 0
    if len(arr) > 1:
        mid = len(arr) // 2
        left_side = arr[:mid]
        right_side = arr[mid:]
        left_count = divide_and_conquer_quadratic(left_side)
        right_count = divide_and_conquer_quadratic(right_side)
        for i in left_side:
            for j in right_side:
                if i < j:
                    count += 1
    return count + left_count + right_count

def divide_and_conquer_nlogn(arr):
    mid = len(arr) // 2
    if not mid:
        return 0
    left = arr[:mid]
    right = arr[mid:]
    count = divide_and_conquer_nlogn(left)
    count += divide_and_conquer_nlogn(right)
    i = 0
    for r in right:
        while i < mid and left[i] < r:
            i += 1
        count += i
    arr[:] = left + right
    arr.sort()  # linear, as Timsort takes advantage of the two sorted runs
    return count

def divide_and_conquer_nlogn_2(arr):
    mid = len(arr) // 2
    if not mid:
        return 0
    left = arr[:mid]
    right = arr[mid:]
    count = divide_and_conquer_nlogn_2(left)
    count += divide_and_conquer_nlogn_2(right)
    i = 0
    arr.clear()
    append = arr.append
    for r in right:
        while i < mid and left[i] < r:
            append(left[i])
            i += 1
        append(r)
        count += i
    arr += left[i:]
    return count

from timeit import timeit
from random import shuffle

arr = list(range(2000))
shuffle(arr)

funcs = [
    original,
    pythonic,
    divide_and_conquer_quadratic,
    divide_and_conquer_nlogn,
    divide_and_conquer_nlogn_2,
]

for func in funcs:
    print(func(arr[:]))

for _ in range(3):
    print()
    for func in funcs:
        arr2 = arr[:]
        t = timeit(lambda: func(arr2), number=1)
        print('%5.1f ms ' % (t * 1e3), func.__name__)