Matplotlib中曲线对齐比较的问题：算法执行时间与理论复杂度曲线的动态缩放方案

我太懂你这个烦恼了——靠单个初始点算出来的缩放因子，在输入规模小的时候可能还凑活，但数据量一大就完全跑偏了。毕竟实际代码的执行时间哪是完美贴合理论复杂度的？小输入时的函数调用开销、缓存命中情况，和大输入时的循环主导开销完全不是一回事，单靠第一个点的比例根本没法覆盖整个区间。

其实解决这个问题的标准做法是用最小二乘法拟合出全局最优的缩放常数，而不是只用单个数据点。这种方法会考虑所有测试数据的误差，找到能让理论曲线和实际曲线整体最贴合的缩放因子，比硬编码或者单点估算靠谱多了。

具体怎么实现？ #

核心思路是：对于每个算法的理论复杂度模型（比如O(n)对应test_list，O(n/2)对应test_list/2，O(√n)对应np.sqrt(test_list)），我们要找到一个常数C，使得C * 理论模型值尽可能接近实际执行时间。最小二乘法就是干这个的——它能帮我们算出这个最优的C。

下面是修改后的完整代码，我把所有曲线整合到同一个图里，方便你对比：

import numpy as np
import matplotlib.pyplot as plt

# 假设你的测试数据已经定义好了
# test_list = np.array([...])
# times_v1 = np.array([...])
# times_v2 = np.array([...])
# times_v3 = np.array([...])

# --- 处理v1: O(n) ---
theoretical_model_v1 = test_list
# 用最小二乘法拟合一次多项式，取一次项系数作为缩放因子C
C_v1 = np.polyfit(theoretical_model_v1, times_v1, 1)[0]
theoretical_v1 = C_v1 * theoretical_model_v1

# --- 处理v2: O(n/2) ---
theoretical_model_v2 = test_list / 2
C_v2 = np.polyfit(theoretical_model_v2, times_v2, 1)[0]
theoretical_v2 = C_v2 * theoretical_model_v2

# --- 处理v3: O(√n) ---
theoretical_model_v3 = np.sqrt(test_list)
C_v3 = np.polyfit(theoretical_model_v3, times_v3, 1)[0]
theoretical_v3 = C_v3 * theoretical_model_v3

# --- 绘制所有曲线到同一个图 ---
plt.figure(figsize=(14, 8))

# 实际执行时间曲线
plt.plot(test_list, times_v1, 'o-', label="v1: O(n) (实际)", color="blue")
plt.plot(test_list, times_v2, 'o-', label="v2: O(n/2) (实际)", color="green")
plt.plot(test_list, times_v3, 'o-', label="v3: O(√n) (实际)", color="red")

# 理论复杂度曲线（缩放后）
plt.plot(test_list, theoretical_v1, '--', label="v1: 理论O(n)", color="blue")
plt.plot(test_list, theoretical_v2, '--', label="v2: 理论O(n/2)", color="green")
plt.plot(test_list, theoretical_v3, '--', label="v3: 理论O(√n)", color="red")

plt.xlabel("输入规模 (n)")
plt.ylabel("执行时间 (ms)")
plt.title("素数检测算法：实际执行时间 vs 理论复杂度")
plt.legend()
plt.grid(True)  # 加个网格更方便看趋势
plt.show()

为什么这个方法更靠谱？ #

• 最小二乘法会综合所有测试点的误差，找到全局最优的缩放因子，而不是只依赖一个可能有偏差的初始点。
• 它能自动抵消实际执行中的一些噪声（比如偶尔的CPU调度延迟），让理论曲线更贴合整体趋势。

额外的小建议 #

1. 多次运行取平均：如果你的执行时间波动比较大，可以对每个输入规模多次运行算法，取平均时间再拟合，这样结果会更稳定。
2. 注意复杂度类的本质：其实O(n/2)和O(n)属于同一个复杂度类，只是常数因子不同。如果你只是想验证复杂度趋势，也可以直接用O(n)的模型来拟合v2的时间，对比常数因子的差异就行。
3. 对数坐标轴：如果输入规模跨度很大（比如从100到100000），可以把x轴或y轴改成对数刻度，这样更容易看清不同复杂度曲线的增长差异。

备注：内容来源于stack exchange，提问作者ConnorRK987