我有一個演算法可以在數字串列中尋找好的配對。一個好的對被認為是索引 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
uj5u.com熱心網友回復：
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__)
uj5u.com熱心網友回復：
最著名的分治演算法之一是歸并排序。而歸并排序實際上是這個演算法的一個很好的基礎。
這個想法是，當比較來自兩個不同“磁區”的兩個數字時，您已經有很多關于這些磁區的剩余部分的資訊，因為它們在每次迭代中都進行了排序。
舉個例子吧！
考慮以下磁區，這些磁區已經單獨排序并且“好對”已被計算在內。
磁區 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) 演算法。
我將把實際的編程作為練習留給你。
uj5u.com熱心網友回復：
@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
uj5u.com熱心網友回復：
就像@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
遞回有時可能很困難，請研究合并排序和快速排序的想法，以更好地了解分而治之演算法的作業原理。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446425.html