如何判断黑箱是多项式还是指数级的

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

如果你的算法的时间成本 t 是关于大小 n 的多项式，也就是说大致可以表示为 t = k*n^m，那么画一个 对数-对数图，也就是把 log t 和 log n 画在一起，应该会是一条直线，斜率是 m（截距是 log k）。

如果你的算法的时间成本 t 是关于大小 n 的指数，也就是说大致可以表示为 t = ke^mn，那么 对数-线性图，也就是把 log t 和 n 画在一起，应该也会是一条直线，斜率是 m（截距是 log k）。

因为这些图都是直线，所以你可以用简单的线性回归来估算这些参数。

我该如何绘制多项式和指数的最佳拟合线？

一旦你得到了参数，直线的斜率 m 和截距 c 在对数-对数图或对数-线性图中，你可以把 m 和 c 转换回原来的坐标空间，从而得到与你原始数据最匹配的曲线（具体细节在下面的示例程序中展示）。

我可以计算哪些指标来判断最佳拟合线的效果？

回归的 R² 值可以给出拟合效果的数值指示，越接近 1 表示拟合效果越好。不过，这个值可能会有点误导，因为它反映的是在变换后的空间中的拟合效果（log t 对 log n 或 log t 对 n），所以直接看结果方程和目测曲线会更简单。另一种定量的衡量方法是计算原始数据和最佳拟合曲线上对应点之间的误差总和。

这个技术在以下数据系列中得到了演示（每个系列都包含噪声）

• 系列 0: t = 3n
• 系列 1: t = 5n²
• 系列 2: t = 7eⁿ
• 系列 3: t = 9e²ⁿ

在下面的图中，你可以看到系列 0 和 1 的多项式形式被恢复了（绿色虚线），而系列 2 和 3 的指数形式也被恢复了（红色虚线）。在每种情况下，较高的 R² 值对应于最佳拟合，参数 m 也被相当准确地恢复了。

代码如下

import math, numpy as np, matplotlib.pyplot as plt
from sklearn import linear_model

N = 100
lo = 2
hi = 25
n = np.linspace(lo,hi,num=N)
D = 4
T = np.maximum(np.random.normal(scale=hi / 25.0, size=(N,D)),0.01)
T[:,0] = 3*(T[:,0] + n)
T[:,1] = 5*(T[:,1] + n)**2
T[:,2] = 7*np.exp(T[:,2]/5.0 + n)
T[:,3] = 9*np.exp(2*(T[:,3]/5.0 + n))

logn = np.log(n)
logT = np.log(T)

for i in range(D):
    # fit log-log model
    loglogmod = linear_model.LinearRegression()
    x=np.reshape(logn,(N,1))
    y=logT[:,i]
    loglogmod.fit(x, y)
    loglogmod_rsquared = loglogmod.score(x, y)
    # fit log model
    logmod = linear_model.LinearRegression()
    x=np.reshape(n,(N,1))
    logmod.fit(x, y)
    logmod_rsquared = logmod.score(x, y)
    # plot results
    plt.subplot(2,2,i+1)
    plt.plot(n, T[:,i], label='series {}'.format(i),lw=2)
    m = loglogmod.coef_[0]
    c = loglogmod.intercept_
    polynomial = math.exp(c)*np.power(n,m)
    plt.plot(n, polynomial,
                label='$t={0:.1f}n^{{{1:.1f}}}$ ($r^2={2:.2f}$)'.format(math.exp(c),m,loglogmod_rsquared),
                ls='dashed',lw=3)
    m = logmod.coef_[0]
    c = logmod.intercept_
    exponential = np.exp(n * m) * math.exp(c)
    plt.plot(n, exponential,
                label='$t={0:.1f}e^{{{1:.1f}n}}$ ($r^2={2:.2f}$)'.format(math.exp(c),m,logmod_rsquared),
                ls='dashed',lw=3)
    plt.legend(loc='upper left', prop={'size':16})

plt.show()

(我使用的文档：sklearn.linear_model.LinearRegression 参考 和 matplotlib 教程)

Answer 2

对你所有的Y值取对数。这样处理后，虽然结果还是多项式的形式，但它会显示出对数增长的特征（因为log x^n = n * log x），而指数曲线会变成一条真正的直线（log exp(x) = x）。

如果你用线性最小二乘法（LSQ）来近似足够多的结果点，那么如果这些点很合适地贴合在一起，你就可以比较确定这个算法是指数级的（不过要允许有一些差异存在，我建议你可以通过观察一个你已知复杂度的算法来经验性地推导出一个合理的epsilon值！），否则就是多项式级的。

你还可以通过检查回归线的偏差来提高信心：如果大多数值都在回归线下面，那么数据很可能是对数级的（也就是说，程序的运行时间是多项式级的）。