使用编程和/或数学计算比较次数并分析特定算法的效率

Question

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和L2的值严格小于L1等)，然后每次进行比较时，我都会增加一个计数器并返回最终计数，然后试图找出输出中的某种模式，但这似乎是一种低效的方法。

有没有一种方法可以像分析合并排序中的经典合并一样计算这一点？

Answer 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)

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

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

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

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

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

总数为

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

我认为这是最糟糕的情况，但你可能会在某个地方再挤出一个。此外，我可能犯了一个错误，在这种情况下，这里的人可能会抓住它。接下来你应该做的是努力证明这是最坏的运行时间。

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

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

• 3，如果L3最小并且L1<L2
• 如果L2最小，则为2
• 如果L1最小，则为1

右边给出了N*6的上界，因为每个列表只能是最小的N次。因此，完成一个证明只需要检查列表变空时会发生什么。

Answer 2

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

在第一个IF中(假设我们将把每次检查布尔值(如done1、done2等)视为单独的比较，并考虑到逻辑表达式通常是以懒惰的方式计算的，那么最坏的情况是永远不会在其他情况之前达到done1＝true(这是有保证的，因为L1的值比L2和L3大)，done2都不达到真(可以保证在L2中具有比在L3中更大的值)，因此L1[i1]<L2[i2]是在每个步骤中计算的。

当L3结束，并且每个周期进入IF部分，并且由于done3为真，所以仅执行4个比较，并且由于懒惰，最后的比较不被计算。当进入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计算))

所以最后的计数是

Len(L3)*12+Len(L2)*10+Len(L1)*7

在对3个阵列进行排序的任何情况下，计算顺序都是相同的，顺序是Len(3)+Len(2)+Ren(1)