归并排序merge_sort函数调用次数为2*n-1而非O(log n)的疑问

你产生误解的核心是混淆了归并排序的递归层数和递归函数总调用次数两个概念：

• 归并排序的递归层数确实是O(log n)量级，以n=8为例，递归深度只有4层，这也是你最初预期打印次数为O(log n)的依据
• 但你把print("hi")放在了函数入口，每次进入merge_sort函数就会触发打印，而merge_sort的总调用次数对应归并排序递归树的总节点数，计算规则为总节点数=2n-1（当n为2的幂时），和你实际测试的结果完全吻合。

以n=8的输入为例拆解调用次数 #

输入长度为8的列表时，递归树共4层，每层的调用次数如下：

• 第1层：1次调用，处理长度为8的完整列表
• 第2层：2次调用，各处理长度为4的子列表
• 第3层：4次调用，各处理长度为2的子列表
• 第4层：8次调用，各处理长度为1的子列表
  总调用次数=1+2+4+8=15，正好是2*8-1，和你实际得到的15次打印结果完全一致。

如果要得到O(log n)量级的打印结果 #

如果想要打印次数和递归层数对齐，可以给函数增加深度参数，每个深度只打印一次即可，参考修改后的代码：

def merge_sort(my_list, depth=0, printed_depth=set()):
    # 每个深度只打印一次
    if depth not in printed_depth:
        print("hi")
        printed_depth.add(depth)
    if(len(my_list) <= 1):
        return
    mid = len(my_list)//2
    l = my_list[:mid]
    r = my_list[mid:]
    merge_sort(l, depth+1, printed_depth)
    merge_sort(r, depth+1, printed_depth)
    # 后续合并逻辑不变

上述代码在n=8的输入下只会打印4次hi，符合O(log n)的量级预期。

内容的提问来源于stack exchange，提问作者Shield77