使用Python实现mergesort排序时执行耗时测量得到异常值问题

核心原因 #

• 计时工具精度不足：你使用的datetime模块时间精度仅到微秒级，而几十元素规模的归并排序本身耗时仅为几微秒，测量误差远大于实际耗时，会出现大量随机波动。
• 单次测量随机干扰大：短耗时任务的测量结果极易受CPU调度、缓存命中、后台进程干扰等影响，单次结果不具备参考性，甚至会出现长数组耗时更短的反常情况。
• 测试数组规模过小：10~100元素的数组排序耗时本身极低，时间数值的随机波动占比极高，无法体现归并排序O(nlogn)的时间复杂度趋势。

改进方案 #

• 更换高精度计时工具：使用Python标准库中的time.perf_counter()替代datetime进行计时，该接口是专门设计用于短时间间隔测量的高精度计时器，精度可达纳秒级。
• 重复多次测量取平均：对每个长度的数组，重复执行排序任务数百到数千次，用总耗时除以执行次数得到平均单次耗时，抵消随机误差影响。
• 增大测试数组规模：将测试数组的长度调整为千级、万级甚至十万级，让排序耗时提升到毫秒甚至秒级，大幅降低误差占比，时间复杂度的趋势会更明显。

参考修改代码 #

import numpy as np
import time

def mergeSort(arr):
    if len(arr) > 1:
        # 取数组中点
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]
        # 递归排序左右子数组
        mergeSort(L)
        mergeSort(R)
        
        i = j = k = 0
        # 合并两个有序子数组
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        # 处理左子数组剩余元素
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        # 处理右子数组剩余元素
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# 随机数组生成器
def arrGen(num):
    return list(np.random.randint(0, 100, size=num))

if __name__ == '__main__':
    # 测试的数组长度
    test_sizes = [1000, 2000, 5000, 10000, 20000]
    # 每个长度重复测试次数
    repeat_times = 5
    for size in test_sizes:
        origin_arr = arrGen(size)
        total_cost = 0
        for _ in range(repeat_times):
            # 每次测试使用数组拷贝，避免有序数组影响结果
            test_arr = origin_arr.copy()
            start = time.perf_counter()
            mergeSort(test_arr)
            end = time.perf_counter()
            total_cost += (end - start) * 1000
        avg_cost = total_cost / repeat_times
        print(f"数组长度：{size:>5}，平均耗时：{avg_cost:.3f}ms")

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