时间戳

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

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

问题描述

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

合并排序（）函数：

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

驱动代码：

#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，这对我来说毫无意义。有人对此有解释吗？

标签： pythontime-complexitymergesort

解决方案

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

当我们查看递归树的一个级别时，我们可以注意到该级别中的每个调用都处理数组的不同分区。该递归级别中的“节点”一起处理数组的所有元素，这使该级别的时间复杂度为 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条件不需要括号

推荐阅读