python - 使复杂性更小(更好)

Question

我有一个算法可以在数字列表中寻找好的对。一个好的配对被认为是索引 i 小于 j 且 arr[i] < arr[j]。目前它的复杂度为 O(n^2)，但我想基于分而治之将其变为 O(nlogn)。我怎样才能做到这一点？

这是算法:

def goodPairs(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

这是我的尝试，但它只返回 0:

def goodPairs(arr):
    count = 0 
    if len(arr) > 1:
         # Finding the mid of the array
        mid = len(arr)//2
  
        # Dividing the array elements
        left_side = arr[:mid]
  
        # into 2 halves
        right_side = arr[mid:]
  
        # Sorting the first half
        goodPairs(left_side)
  
        # Sorting the second half
        goodPairs(right_side)

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

Answer 1

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

代码(Try it online!):

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__)