如何将解决方案转化为分治(寻找具有最大，最小值的子数组)

Question

我正试图在分治算法方面做得更好，我用下面这个作为例子。给定一个数组_in和一些长度l，它找到子数组_in[_min_start,_min_start+l]的起始点，使得该子数组中的最低值是它可能达到的最高值。我想出了一个无分而治之的解决方案，我想知道如何把它转换成一个把数组分成更小的部分(分而治之)。

def main(_in, l):
_min_start = 0
min_trough = None
for i in range(len(_in)+1-l):
if min_trough is None:
min_trough = min(_in[i:i+l])

if min(_in[i:i+l]) > min_trough:
_min_start = i
min_trough = min(_in[i:i+l])

return _min_start, _in[_min_start:_min_start+l]

。对于数组[5, 1, -1, 2, 5, -4, 3, 9, 8, -2, 0, 6]和长度为3的子数组，它将返回起始位置6(结果是数组[3,9,8])。

Answer 1

三个0 (n)解决方案和一个基准

注意我将_in和l重命名为更清晰的名称A和k。

解决方案1:分而治之

将数组分成两半。递归地解左半部分和右半部分。尚未考虑的子数组穿过中间，也就是说，它们是左边部分的后缀加上右边部分的前缀。计算左半部分的k-1个前缀最小值和右半部分的k-1个前缀最小值。这样就可以在O(1)次时间内计算出每个长度为k的中间交叉子数组的最小值。整个数组的最佳子数组是左最佳、右最佳和交叉最佳的最佳。

运行时间是O(n)，我相信。正如Ellis所指出的，在递归中，子数组可以变得小于k。这种情况需要O(1)时间来返回的等量;这里的中没有任何长度为k的子数组。所以时间是:

T(n) = { 2 * T(n/2) + O(k)    if n >= k
{ O(1)                 otherwise

对于任意0 <= k <= n，我们有k=n^c且0 <= c <= 1。那么调用的次数是Θ(n^1-c)，每个调用自己的工作需要Θ(n^c)时间，总共Θ(n)时间。

发布了一个关于复杂性的问题。

Python实现:

def solve_divide_and_conquer(A, k):
def solve(start, stop):
if stop - start < k:
return -inf,
mid = (start + stop) // 2
left = solve(start, mid)
right = solve(mid, stop)
i0 = mid - k + 1
prefixes = accumulate(A[mid:mid+k-1], min)
if i0 < 0:
prefixes = [*prefixes][-i0:]
i0 = 0
suffixes = list(accumulate(A[i0:mid][::-1], min))[::-1]
crossing = max(zip(map(min, suffixes, prefixes), count(i0)))
return max(left, right, crossing)
return solve(0, len(A))[1]

解2:k-Blocks

@benrg评论,上面的分而治之是不必要的复杂。我们可以简单地处理长度为k的块。计算第一个块的后缀最小值和第二个块的前缀最小值。这允许在O(1)时间内找到这两个块中每个k长度子数组的最小值。第二和第三块，第三和第四块，等等。时间是O (n)。

Python实现:

def solve_blocks(A, k):
return max(max(zip(map(min, prefixes, suffixes), count(mid-k)))
for mid in range(k, len(A)+1, k)
for prefixes in [accumulate(A[mid:mid+k], min, initial=inf)]
for suffixes in [list(accumulate(A[mid-k:mid][::-1], min, initial=inf))[::-1]]
)[1]

方案3:MonoqueueNotdivide &但我想到的第一个(并且知道是O(n))。

滑动窗口，表示窗口中数组值严格递增的(排序)索引队列。当滑动窗口包括一个新值A[i]:

1. 如果滑动使deque掉出窗口，则从deque中删除第一个索引。
2. 删除数组值大于A[i]的索引。(它们再也不能是窗口的最小值了。)
3. 新增索引i
仍然在队列中的第一个索引是当前窗口最小值的索引。使用它来更新整体结果。Python实现:

from collections import deque
A = [5, 1, -1, 2, 5, -4, 3, 9, 8, -2, 0, 6]
k = 3
I = deque()
for i in range(len(A)):
if I and I[0] == i - k:
I.popleft()
while I and A[I[-1]] >= A[i]:
I.pop()
I.append(i)
curr_min = A[I[0]]
if i == k-1 or i > k-1 and curr_min > max_min:
result = i - k + 1
max_min = curr_min
print(result)

基准

从0到9999的4000个数字，k=2000:

80.4 ms   81.4 ms   81.8 ms  solve_brute_force
80.2 ms   80.5 ms   80.7 ms  solve_original
2.4 ms    2.4 ms    2.4 ms  solve_monoqueue
2.4 ms    2.4 ms    2.4 ms  solve_divide_and_conquer
1.3 ms    1.4 ms    1.4 ms  solve_blocks

基准代码(在线试用!):

from timeit import repeat
from random import choices
from itertools import accumulate
from math import inf
from itertools import count
from collections import deque
def solve_monoqueue(A, k):
I = deque()
for i in range(len(A)):
if I and I[0] == i - k:
I.popleft()
while I and A[I[-1]] >= A[i]:
I.pop()
I.append(i)
curr_min = A[I[0]]
if i == k-1 or i > k-1 and curr_min > max_min:
result = i - k + 1
max_min = curr_min
return result
def solve_divide_and_conquer(A, k):
def solve(start, stop):
if stop - start < k:
return -inf,
mid = (start + stop) // 2
left = solve(start, mid)
right = solve(mid, stop)
i0 = mid - k + 1
prefixes = accumulate(A[mid:mid+k-1], min)
if i0 < 0:
prefixes = [*prefixes][-i0:]
i0 = 0
suffixes = list(accumulate(A[i0:mid][::-1], min))[::-1]
crossing = max(zip(map(min, suffixes, prefixes), count(i0)))
return max(left, right, crossing)
return solve(0, len(A))[1]
def solve_blocks(A, k):
return max(max(zip(map(min, prefixes, suffixes), count(mid-k)))
for mid in range(k, len(A)+1, k)
for prefixes in [accumulate(A[mid:mid+k], min, initial=inf)]
for suffixes in [list(accumulate(A[mid-k:mid][::-1], min, initial=inf))[::-1]]
)[1]

def solve_brute_force(A, k):
return max(range(len(A)+1-k),
key=lambda start: min(A[start : start+k]))
def solve_original(_in, l):
_min_start = 0
min_trough = None
for i in range(len(_in)+1-l):
if min_trough is None:
min_trough = min(_in[i:i+l])

if min(_in[i:i+l]) > min_trough:
_min_start = i
min_trough = min(_in[i:i+l])

return _min_start  # , _in[_min_start:_min_start+l]
solutions = [
solve_brute_force,
solve_original,
solve_monoqueue,
solve_divide_and_conquer,
solve_blocks,
]
for _ in range(3):
A = choices(range(10000), k=4000)
k = 2000
# Check correctness
expect = None
for solution in solutions:
index = solution(A.copy(), k)
assert 0 <= index and index + k-1 < len(A)
min_there = min(A[index : index+k])
if expect is None:
expect = min_there
print(expect)
else:
print(min_there == expect, solution.__name__)
print()
# Speed
for solution in solutions:
copy = A.copy()
ts = sorted(repeat(lambda: solution(copy, k), number=1))[:3]
print(*('%5.1f ms ' % (t * 1e3) for t in ts), solution.__name__)
print()