如何在Python中准确计算算法时间复杂度及解决运行时波动问题

运行时间波动的原因 #

• 系统环境干扰：Python解释器的垃圾回收（GC）、操作系统后台进程（如磁盘IO、其他应用）会抢占CPU资源，导致单次运行时间出现随机波动。
• 小输入的测量误差：你当前测试的graph1规模极小，算法运行时间仅几微秒，即便time.perf_counter()精度很高，微小的系统波动也会让结果差异明显。
• 代码笔误：代码中调用了dijkstra(graph6, start_vertex)，但只定义了graph1，这会引发运行错误，需先修正该问题才能正常测试。

准确测量的实用方法 #

• 多次运行取统计值：对同一输入重复运行算法几十甚至上百次，取平均值或中位数——中位数比平均值更能抵抗极端值的干扰，结果更稳定。
• 跳过首次运行：首次运行时，Python解释器可能会进行模块加载、字节码编译等操作，耗时偏高，建议忽略第一次的结果。
• 使用timeit模块：Python内置的timeit专门用于代码计时，它会自动处理多次运行，还能屏蔽部分系统干扰，是论文实验中常用的工具。
• 测试更大规模的输入：时间复杂度分析需要观察输入规模增长时的运行时间变化趋势。用包含几十、几百甚至上千个节点的图测试，结果的稳定性和参考性会更强。
• 临时禁用垃圾回收：测量前关闭GC，避免其在算法运行过程中触发，进一步减少干扰（测试完成后记得恢复）。

改进后的代码示例 #

方法1：手动多次运行取平均

import time
import heapq
import gc

def dijkstra(graph, source):
    dist = {vertex: float('infinity') for vertex in graph}
    visited = set()
    dist[source] = 0
    priority_queue = [(0, source)]
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        if current_vertex in visited:
            continue
        visited.add(current_vertex)
        for neighbor, edge_weight in graph[current_vertex].items():
            if neighbor in visited:
                continue
            alt = dist[current_vertex] + edge_weight
            if alt < dist[neighbor]:
                dist[neighbor] = alt
                heapq.heappush(priority_queue, (alt, neighbor))
    return dist

# 修正笔误，使用正确的graph1
graph1 = {
    'A': {'B': 1},
    'B': {'A': 1}
}

start_vertex = 'A'
num_runs = 100
total_time = 0

# 禁用GC减少干扰
gc.disable()
# 跳过首次运行，排除初始化耗时
dijkstra(graph1, start_vertex)

for _ in range(num_runs):
    start_time = time.perf_counter()
    distances = dijkstra(graph1, start_vertex)
    end_time = time.perf_counter()
    total_time += (end_time - start_time) * 1e6

# 恢复GC
gc.enable()

avg_time = total_time / num_runs
print(f"{num_runs}次运行平均耗时: {avg_time:.2f} 微秒")

方法2：使用timeit模块

import timeit
import heapq

def dijkstra(graph, source):
    dist = {vertex: float('infinity') for vertex in graph}
    visited = set()
    dist[source] = 0
    priority_queue = [(0, source)]
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        if current_vertex in visited:
            continue
        visited.add(current_vertex)
        for neighbor, edge_weight in graph[current_vertex].items():
            if neighbor in visited:
                continue
            alt = dist[current_vertex] + edge_weight
            if alt < dist[neighbor]:
                dist[neighbor] = alt
                heapq.heappush(priority_queue, (alt, neighbor))
    return dist

graph1 = {
    'A': {'B': 1},
    'B': {'A': 1}
}

start_vertex = 'A'

# timeit自动运行指定次数，返回总耗时（秒）
total_time = timeit.timeit(
    lambda: dijkstra(graph1, start_vertex),
    number=100
)

avg_time = (total_time / 100) * 1e6
print(f"100次运行平均耗时: {avg_time:.2f} 微秒")

关于时间复杂度验证 #

除了测量运行时间，还可以通过输入规模与运行时间的拟合分析验证复杂度：

• 生成不同规模的随机图（比如节点数n从10到1000，按稀疏/稠密图设置边数）
• 测量每个规模下的平均运行时间
• 绘制n vs 运行时间的曲线，观察是否符合Dijkstra算法的O(M log N)复杂度（M为边数，N为节点数）

内容的提问来源于stack exchange，提问作者محمد