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

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）