归并排序的时间复杂度：函数似乎被调用了 2*n-1 次而不是 O(log n) 次

Question

我正在教授编码 class，需要一种直观且明显的方式来解释归并排序的时间复杂度。我尝试在 merge_sort() 函数的开头包含一个打印语句，预计该打印语句将执行 O(log n) 次。但是，据我所知，它执行了 2*n-1 次（下面的 Python 代码）：

merge_sort() 函数:

def merge_sort(my_list):
    print("hi") #prints 2*n-1 times??
    if(len(my_list) <= 1):
        return
    mid = len(my_list)//2
    l = my_list[:mid]
    r = my_list[mid:]
    merge_sort(l)
    merge_sort(r)
    i = 0
    j = 0
    k = 0
    while(i < len(l) or j < len(r)):
        #print("hey") #prints nlogn times as expected
        if(i >= len(l)):
            my_list[k] = r[j]
            j += 1
        elif(j >= len(r)):
            my_list[k] = l[i]
            i += 1
        elif(l[i] < r[j]):
            my_list[k] = l[i]
            i += 1
        elif(l[i] > r[j]):
            my_list[k] = r[j]
            j += 1
        k += 1

Driver代码：

#print("Enter a list")
my_list = list(map(int, input().split()))
#print("Sorted list:")
#merge_sort(my_list)
print(my_list)

输入：

1 2 3 4 5 6 7 8

预期输出：

hi
hi
hi

或其一些与 log n 成比例变化的变体。

实际输出：

hi
hi
hi
hi
hi
hi
hi
hi
hi
hi
hi
hi
hi
hi
hi #15 times, i.e. 2*n-1

用不同的输入大小对它进行多次迭代，给我的印象是这是 2*n-1，这对我来说毫无意义。有人对此有解释吗？

Answer 1

只有O(logn)次递归调用是不正确的。 O(logn) 的东西是递归树的深度，而不是递归树中节点的数量。

当我们查看递归树的一个层时，我们可以注意到那个层中的每个调用都处理一个不同的数组的分区。该递归级别中的“节点”一起处理数组的所有元素，这为 level 提供了 O(n) 时间复杂度。每个级别都是如此。

由于有 O(logn) 个级别，因此总复杂度归结为 O(nlogn)。

这里有一个关于如何说明这一点的建议：

statistics = []

def merge_sort(my_list, depth=0):
    if len(my_list) <= 1:
        return
    # manage statistics
    if depth >= len(statistics):
        statistics.append(0)  # for each depth we count operations
    mid = len(my_list)//2
    l = my_list[:mid]
    r = my_list[mid:]
    merge_sort(l, depth+1)
    merge_sort(r, depth+1)
    i = 0
    j = 0
    k = 0
    while i < len(l) or j < len(r):
        statistics[depth] += 1  # count this as a O(1) unit of work
        if i >= len(l):
            my_list[k] = r[j]
            j += 1
        elif j >= len(r):
            my_list[k] = l[i]
            i += 1
        elif l[i] < r[j]:
            my_list[k] = l[i]
            i += 1
        elif l[i] > r[j]:
            my_list[k] = r[j]
            j += 1
        k += 1

import random

my_list = list(range(32))
random.shuffle(my_list)
merge_sort(my_list)
print(my_list)
print(statistics)

统计信息将输出每个级别完成的工作单元数。在输入大小为 32 的示例中，您将得到一个包含 5 个这样的数字的列表。

注意：在 Python 中，if 条件不需要括号

归并排序的时间复杂度：函数似乎被调用了 2*n-1 次而不是 O(log n) 次

Time complexity of merge sort: function appears to be called 2*n-1 times rather than O(log n) times

python

mergesort

time-complexity