python - 如何确定黑盒是多项式还是指数

Question

我有一个问题，基本上可以简化为:

1. 你有一个接受长度为 n 的输入的黑盒函数。
2. 您可以测量函数返回答案所花费的时间，但您无法确切地看到它是如何计算的。
3. 您必须确定此函数的时间复杂度是多项式还是指数。

我这样做的方法是通过函数运行数千个不同长度的随机样本输入，然后将它们绘制在散点图上，y 轴为时间，x 轴为输入长度。

我使用 numpy 绘制了散点图，但现在如何绘制多项式和指数最佳拟合线？我可以计算哪些指标来确定哪些最佳拟合线最适合？

(提出了一个类似的问题，但理论上并没有强调计算机科学的特定语言:https://cs.stackexchange.com/questions/23686/how-to-determine-if-a-black-box-is-polynomial-or-exponential)

Answer 1

取所有 Y 值的对数。多项式结果仍将呈现对数增长(因为 log x^n = n * log x)，但指数曲线将转换为适当的直线(log exp(x) = x )。

如果您现在使用线性 LSQ 近似足够多的结果点，那么您可以非常确定该算法是指数的，如果它很好地拟合(尽管允许存在一些差异——我建议根据经验推导出一些合理的 epsilon检查您知道其复杂性的算法!)，否则为多项式。

您还可以通过检查与回归线的偏差来稍微提高置信度:如果大多数值都低于它，那么数据很可能是对数的(即程序以多项式时间运行)。