ste*_*del 5 python statistics numpy matplotlib time-complexity
我有一个问题,基本上减少到这个:
我这样做的方法是通过函数运行数千个不同长度的随机样本输入,然后在散点图上绘制它们,在y轴上有时间,在x轴上有输入长度.
我有使用numpy绘制的散点图,但现在我如何绘制多项式和指数最佳拟合线？我可以计算哪些指标来确定哪条最佳拟合线最适合？
(问一个类似的问题,但理论上并没有强调计算机科学上的特定语言:https://cs.stackexchange.com/questions/23686/how-to-determine-if-a-black-box-is-polynomial-或指数)
取所有Y值的对数.多项式结果仍将显示对数增长(因为log x^n = n * log x),但指数曲线将转换为适当的直线(log exp(x) = x).
如果你现在用线性LSQ近似得到足够的结果点,那么你可以非常肯定算法是指数的,如果它很好地适合(允许存在一些差异 - 我建议通过检查算法凭经验推导出一些合理的epsilon)你知道!)的复杂性,否则就知道多项式.
您还可以通过检查与回归线的偏差来稍微提高置信度:如果大多数值低于它,那么数据很可能是对数的(即程序以多项式时间运行).
| 归档时间： |
|
| 查看次数： |
755 次 |
| 最近记录： |