如何判断算法是多项式还是指数级缩放？多项式最高阶是多少？

算法缩放类型判定及拟合问题解答 #

1. 多项式拟合chi2值更小是否等于算法为多项式级缩放

仅靠chi2值无法直接判定算法缩放类型。chi2仅反映当前采样的输入规模区间内，拟合函数和实测数据的匹配程度，小范围输入下，低阶指数函数也能和多项式拟合出接近的chi2结果。
正确的区分方法优先看坐标拟合结果：

• 若**半对数坐标（x为输入规模n，y为对数耗时log(t)）**下拟合为直线，属于指数级缩放
• 若**双对数坐标（x为log(n)，y为log(t)）**下拟合为直线，属于多项式级缩放
  你补充的对数y轴图可以作为第一步判定的依据。

2. 高次多项式过拟合问题的处理

高次多项式拟合效果更好是正常现象：阶数越高拟合自由度越高，会额外拟合测试过程中的噪声（如缓存命中波动、系统调度开销、测量误差等），和算法本身的时间复杂度无关。
可以通过以下方法避免过拟合选到正确的阶数：

• 先通过双对数坐标的斜率估算多项式阶数，优先拟合和该估算值接近的阶数，不要盲目测试过高阶数
• 统计拟合后高阶项的系数置信区间，若置信区间包含0，说明该高阶项无统计显著性，可以直接剔除
• 用AIC/BIC信息准则选择最优阶数，这类准则会在拟合优度和模型复杂度之间做权衡，不会无脑选最高阶
• 做交叉验证：把实测数据拆分为训练集和验证集，选择验证集上误差最小的阶数

3. 拟合p值恒为1的含义

p值恒为1大概率是两种原因导致的：

• 自由度设置错误：你使用的scipy.stats.chisquare默认自由度为「样本点数-1」，但卡方拟合优度检验的正确自由度应为「样本点数 - 拟合参数个数」（比如2阶多项式有3个参数：二次项、一次项、常数项，对应参数个数为3），未扣除拟合参数的自由度会直接导致p值计算异常
• 你的测试数据噪声极低，拟合残差远小于测量误差范围，卡方统计量趋近于0，对应p值就会趋近于1，说明拟合残差完全符合随机波动的预期，不同拟合方式的差异没有达到统计显著性水平

实操建议 #

• 扩大输入规模测试区间：时间复杂度是n足够大时的渐近特性，小范围输入下常数项、低阶项、系统开销的占比太高，无法准确判定缩放类型
• 排除异常值干扰：多次测量同一输入规模下的耗时取平均值，降低随机噪声影响
  内容的提问来源于stack exchange，提问作者AlphaBetaGamma96