使复杂性更小（更好）

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

这是我的尝试，但它只是 returns 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

最 well-known divide-and-conquer 算法之一是归并排序。归并排序实际上是这个算法的一个很好的基础。

这个想法是，当比较来自两个不同 'partitions' 的两个数字时，您已经掌握了这些分区剩余部分的大量信息，因为它们在每次迭代中都已排序。

举个例子吧！

考虑以下分区，这些分区已经单独排序，并且计算了“好对”。

分区 x: [1, 3, 6, 9].

分区 y: [4, 5, 7, 8].

重要的是要注意分区 x 中的数字在原始列表中比分区 y 更靠左。特别是，对于 x 中的每个元素，它对应的索引 i 必须小于 y 中每个元素的某个索引 j。

我们将从比较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)的算法。

我会将实际的编程作为练习留给你。

Answer 2

@niklasaa 添加了对合并排序类比的解释，但您的实现仍然存在问题。

您正在对数组进行分区并计算两半的结果，但是

你实际上没有对任何一半进行排序。因此，当您比较它们的元素时，您的双指针方法是不正确的。
你还没有在最后的计算中使用他们的结果。这就是您得到错误答案的原因。

对于第 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

Answer 3

就像@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

递归有时会很困难，请研究归并排序和快速排序的思想，以更好地了解分而治之算法的工作原理。

Answer 4

Fire Assassin 先前接受的 ~~current~~ 答案并没有真正回答这个问题，它要求更好的复杂性。它仍然是二次解，并且与更简单的二次解一样快。具有 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__)

使复杂性更小（更好）

Making the complexity smaller (better)

python

algorithm

time-complexity