10

I am trying to solve this problem..

Given a list of n numbers, we would like to find the smallest and the second smallest numbers from the list. Describe a divide-and-conquer algorithm to solve this problem. Assume that n = 2^k for an integer k. The number of comparisons using your algorithm should not be more than 3n/2 − 2, even in the worst case.

My current solution is to use select algorithm to get the median and then divide the list into L1( contains element less than or equal to the median), R ( median), L2 ( contains all the elements grater than median). Is it correct? If so, what should I do next?

4

2 回答 2

9

请注意，中值选择算法使用 Θ(n) 比较，但这并不意味着它最多使用 3n/2 - 2 次比较。实际上，我认为它使用的更多，这可能会排除您的解决方案策略。

作为提示：将此问题视为为所有 2 k建立淘汰赛；每轮的获胜者（两个数字中较小的一个）进入下一轮。实现它需要多少次比较？接下来，请注意第二小的数字必须“丢失”到最小的数字。第二小数也是“输”到最小数的最小数。鉴于此，你能有效地找到第二小的数字吗？

希望这可以帮助！

于 2013-10-16T23:42:31.383 回答
3

哦，我只是理解它（在 Python 中）：

def two_min(arr):
    n = len(arr)
    if n==2: # Oops, we don't consider this as comparison, right?
        if arr[0]<arr[1]:                   # Line 1
            return (arr[0], arr[1])
        else:
            return (arr[1], arr[0])
    (least_left, sec_least_left) = two_min(arr[0:n/2])
    (least_right, sec_least_right) = two_min(arr[n/2:])
    if least_left < least_right:            # Line 2
        least = least_left
        if least_right < sec_least_left:    # Line 3
            return (least, least_right)
        else:
            return (least, sec_least_left)
    else:
        least = least_right
        if least_left < sec_least_right:    # Line 4
            return (least, least_left)
        else:
            return (least, sec_least_right)

总共：

第 1 行：会有确切的n/2比较

第2行：这里会有n/4 + n/8 + ... + 1比较

第 3 行和第 4 行：每次调用都会执行其中的一个two_min（除非使用两个元素调用它）。我们two_min用总n-1次数跟注（因为有那么多锦标赛），n/2其中有两个元素被跟注。所以第 3 行和第 4 行有助于n/2 - 1比较

结合所有这些，我们有：

total_comparisons = n/2 + (n/4 + n/8 + ... + 1) + (n/2 - 1)
                  = (n - 1) + (n/2 - 1)
                  = 3n/2 - 2
于 2013-10-17T10:56:49.213 回答