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

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更小。

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

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

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