1 
def three_way_merge(L1,L2,L3):
    L = []
    i1 = 0
    i2 = 0
    i3 = 0
    done1 = False
    done2 = False
    done3 = False
    while not (done1 and done2 and done3):
        if not done1 and (done2 or L1[i1] < L2[i2]) and (done3 or L1[i1] < L3[i3]):
            L.append(L1[i1])
            i1 += 1
            done1 = i1 >= len(L1)
        elif not done2 and (done3 or L2[i2] < L3[i3]):
            L.append(L2[i2])
            i2 += 1
            done2 = i2 >= len(L2)
        else:
            L.append(L3[i3])
            i3 += 1
            done3 = i3 >= len(L3)
    return L

我想计算我发现的该算法的最差比较次数，因为我的算法课即将进行考试，我希望能够进行这种分析。我的想法是编写一个程序来创建这种“最坏情况”的许多随机示例（我猜这是类型：L1 = [9,10,11], L2 = [6,7,8], L3 = [3,4,5]，其中所有列表都已排序，但值严格小于L3等）然后每个当我进行任何比较时，我会增加一个计数器并返回最终计数，然后尝试找出输出中的某种模式，但这似乎是一种低效的方法。L2L1

有没有办法以类似于归并排序中经典归并分析的方式来计算这一点？

4

2 回答 2

1

作为一般规则，生成随机输入并不是计算最坏情况运行时间的好方法。例如，快速排序平均在 O(n log n) 中运行，但在最坏的情况下它在 O(n^2) 中运行。但是，即使您生成了大量随机样本，对于中等大小的 n，您也永远不会接近最坏的情况。相反，尝试手动构建最坏情况输入。

在这种情况下，假设每个数组的长度为 N，似乎最坏的情况发生在

L1 = (N,2N,2N+1,...,3N-3,3N)
L2 = (N+1,N+2,...,2N-1,3N-1)
L3 = (1,2,...,N-1,3N-2)

要了解原因，请跟踪算法的执行情况。发生的第一件事是将 的前 N-1 个元素L3添加到L. 循环的每一次迭代都将进行 3 次比较：第一个语句中的两个if和第二个语句中的一个。请注意，我们需要L1[1]<L2[1]否则它将跳过第一个比较中的第二个比较if

接下来是 element L[1]=N，它只进行一次比较。

在此之后是 的前 N-1 个元素L[2]，每个元素都需要两次比较，一次到L1和一次到L3。

接下来是来自 的接下来的 N-2 个元素L1，每个元素都有一个比较。

此时，每个列表中只剩下一个元素。 L3首先被选中，进行 3 次比较，然后进行 1 次比较L2，仅此而已。

总数是

(N-1)*(3+2+1)+3+1 = 6N - 2

我认为这是最坏的情况，但你也许可以在某个地方再挤出一个。另外，我可能犯了一个错误，在这种情况下，这里有人可能会抓住它。接下来你应该做的是尝试实际证明这是最坏情况下的运行时间。

PS 这个算法对于合并三个列表不是最优的。从三个列表的前面选择最小的元素最多只需要 2 次比较，而不是 3 次。如果你找到了L2<L1，L1<L3那么就没有必要比较了L2，L3因为你已经知道它L2更小了。

编辑时：证明这实际上是最坏的情况应该不难。假设没有列表为空，则每次迭代的比较次数为：

  • 3 如果 L3 最小且 L1 < L2
  • 2 如果 L2 最小
  • 1 如果 L1 最小

那里给你一个 N*6 的上限，因为每个列表只能是最小的 N 次。因此，完成证明只需要检查列表变为空的最后会发生什么。

于 2013-10-01T18:19:31.943 回答
0

正如您所说，最糟糕的情况是 L3（或 L2）的所有数字都小于 L1，因为 IF 子句将失败并且它将执行 elif 部分计算更多比较。

在第一个 IF 内部（假设我们将每次检查布尔值（如 done1、done2 等）都算作一个单独的比较）并考虑到逻辑表达式通常是以惰性方式计算的，那么最坏的情况是永远不会在其他人之前达到 done1 = true （保证 L1 的值大于 L2 和 L3）， done2 都没有达到 true （可以保证 L2 中的值大于 L3 中的值），因此 L1[i1] < L2[i2]在每一步中计算。

当 L3 完成时，每个循环进入 IF 部分，只执行 4 次比较，因为 done3 为真，并且由于惰性，最后一次比较没有计算。进入 elif 部分时也是如此，仅执行 2 次比较。

当 L2 完成时，IF 子句中只进行 3 次比较（因为 done2 和 done3 为真）

所以，有了这个配置（L1 >> L2 >> L3），这个算法将执行：

Len(L3) * (3 (while 子句) + 5 (IF 子句) + 3 (elif 部分) + 1 (done3 计算)) + Len(L2) * (3 (while 子句) + 4 ( IF 子句) + 2 (elif 部分) + 1 (done2 计算) + Len(L1) * (3 (while 子句) + 3 (IF 子句) + 1 (done1 计算))

所以最终的计数是

长度(L3) * 12 + 长度(L2) * 10 + 长度(L1) * 7

计算顺序在任何情况下都是相同的 3 个数组的排序，顺序是 Len(3) + Len(2) + Len(1)

于 2013-10-01T18:56:01.607 回答