recursion - 将递归转化为分而治之

Question

我正在尝试返回列表中最小的三个项目。以下是我编写的 O(n) 解决方案：

def three_smallest(L):
    # base case
    if (len(L) == 3):
        return sorted(L)
        
    current = L[0]
    (first_smallest,second_smallest,third_smallest) = three_smallest(L[1:])
    
    if (current < first_smallest):
        return (current, first_smallest, second_smallest)
    elif (current < second_smallest):
        return (first_smallest, current, second_smallest)
    elif (current < third_smallest):
        return (first_smallest, second_smallest, current)
    else:
        return (first_smallest,second_smallest,third_smallest)

现在我正在尝试编写一种分而治之的方法，但我不确定应该如何划分列表。任何帮助，将不胜感激。

请注意，这个解决方案（据我所知）不是分而治之。它只是一个基本的递归解决方案，因为分而治之涉及将长度为 n 的列表除以整数 b，并在这些部分上调用算法。

标签： recursiondivide-and-conquer

Answer 1

对于分而治之，您通常希望将一组（大致）分成两半，而不是一个一个地削减它。也许以下内容可以满足您的需求？

def three_smallest(L):
    if (len(L) <= 3):    # base case, technically up to 3 (can be fewer)
        return sorted(L)        
    mid = len(L) // 2    # find the midpoint of L
    # find (up to) the 3 smallest in first half, ditto for the second half, pool
    # them to a list with no more than 6 items, sort, and return the 3 smallest
    return sorted(three_smallest(L[:mid]) + three_smallest(L[mid:]))[:3]

请注意，由于基本情况的不等式，此实现没有最小列表大小要求。

在规模的另一端，您的原始实现仅限于具有少于一千个值的列表，否则它将破坏递归堆栈。上面给出的实现能够毫无问题地处理一百万个值的列表。