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
等),然后每次我做任何比较时,我都会递增一个计数器并返回最终计数,然后尝试找出输出中的某种模式,但这似乎是一种低效的方法这个。
有没有办法以类似于归并排序中经典归并的分析的方式来计算它?
最佳答案
作为一般规则,生成随机输入并不是计算最坏情况运行时间的好方法。例如,快速排序平均在 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
更小。
关于编辑:证明这实际上是最坏的情况应该不难。假设所有列表都不为空,则每次迭代的比较次数为:
- 如果 L3 最小且 L1 < L2 则为 3
- 如果L2最小则为2
- 如果 L1 最小则为 1
就在那里给你一个上限 N*6,因为每个列表只能是最小的 N 次。因此,完成一个证明只需要检查列表变空的末尾发生了什么。
关于python - 使用编程和/或数学计算比较次数并分析特定算法的效率,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19122201/