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

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

有没有一种方法可以用类似于分析merge-in-merge-sort的方法来计算这个值？在

Answer 1

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

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

当L3完成时，每个循环进入IF部分，由于done3为真，因此只执行4次比较，由于懒惰，最后一次比较不计算。当进入elif部分时同样适用，只执行2次比较。在

当L2完成时，IF子句中只执行3个比较（因为done2和done3为true）

因此，有了这种配置（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）

Answer 2

一般来说，生成随机输入并不是计算最坏情况下运行时间的好方法。例如，快速排序平均在O（n logn）中运行，但在最坏的情况下，它在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进行一个比较，就这样。在

总数是

^{pr2}$

我认为这是最坏的情况，但你也许可以从中挤出一个。另外，我可能犯了一个错误，在这种情况下，这里的人可能会抓住它。下一步你应该做的是试着证明这是最坏情况下的运行时间。在

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

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

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

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