Python绘制MergeSort执行时间与nlogn对比曲线不符合预期

问题根因 #

你的代码存在两个核心问题，导致曲线和预期不符：

• 测试逻辑错误：数组arr没有在每次测试不同规模时重置，上一次排序后的有序元素会残留，加上数组持续追加元素，导致测量的耗时不准；且单次运行测量时间受系统波动影响大，结果不稳定。
• 对比逻辑错误：O(nlogn)是渐近时间复杂度，仅描述耗时随数据规模增长的趋势，不存在和实际运行时间（秒）直接对应的绝对数值。你直接计算i*log2(i)的原始值，对于n=3000的规模这个值约为34650，而实际排序3000个元素仅需零点零几秒，二者差了5个数量级，自然实际耗时曲线看起来贴在x轴上，无法匹配趋势。

修正后代码 #

from random import randint
from math import log2
import timeit
import matplotlib.pyplot as plt


def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2
    for i in range(n1):
        L[i] = arr[l + i]
    for j in range(n2):
        R[j] = arr[m + 1 + j]

    i = 0    # 第一个子数组的起始索引
    j = 0    # 第二个子数组的起始索引
    k = l    # 合并后数组的起始索引

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # 拷贝左子数组剩余元素
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # 拷贝右子数组剩余元素
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1


def mergeSort(arr, l, r):
    if l < r:
        m = l + (r - l) // 2
        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, m, r)


if __name__ == "__main__":
    x = []
    actual_time = []
    theory_nlogn = []
    scale_factor = None  # 理论值缩放系数，用于对齐实际时间的量级
    test_repeat = 3  # 每个规模重复测试次数，取平均降低误差

    # 测试规模从100到3000，步长100
    for n in range(100, 3001, 100):
        total_cost = 0
        for _ in range(test_repeat):
            # 每次测试生成全新的随机乱序数组，避免有序残留影响结果
            test_arr = [randint(0, n) for _ in range(n)]
            start = timeit.default_timer()
            mergeSort(test_arr, 0, n - 1)
            end = timeit.default_timer()
            total_cost += (end - start)
        avg_cost = total_cost / test_repeat
        x.append(n)
        actual_time.append(avg_cost)
        # 用第一个测试点计算缩放系数，保证理论值和实际值量级一致
        if scale_factor is None:
            scale_factor = avg_cost / (n * log2(n))
        theory_nlogn.append(scale_factor * n * log2(n))

    plt.plot(x, actual_time, label='归并排序实际耗时')
    plt.plot(x, theory_nlogn, label='nlogn理论趋势（缩放后）', linestyle='--')
    plt.legend()
    plt.xlabel('数组规模n')
    plt.ylabel('执行时间 (s)')
    plt.title('归并排序耗时与nlogn理论值对比')
    plt.show()

修改点说明 #

• 每个规模测试前都生成全新的随机数组，完全避免之前排序结果的干扰，保证每次测试的输入都是随机乱序
• 每个规模重复测试3次取平均耗时，降低系统资源调度等偶然因素带来的测量误差
• 引入常数缩放因子对nlogn理论值做量级对齐，因为复杂度分析省略了常数项，这个常数项和编程语言、硬件性能、代码实现都有关系，对齐后可以直观看到两条曲线的增长趋势完全吻合
• 移除了n=1的无效测试点（log2(1)=0，无趋势对比意义）

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