algorithm - 我如何估计功能的增长？

Question

<分区>

Answer 1

绘制数据是一个好的开始；如果您在线性尺度和对数尺度上绘制它，您可能能够区分多项式增长函数和指数增长函数。

为了快速估计复杂度的顺序，计算时间增加的比率。来自命令

dc -e '46656 7776/ 16480.96 89.73/  7776 1296/ 89.73 0.48/f'

输出

186
6
183
6

或者python命令

python -c 'print 46656/7776, 16481/90, 7776/1296, 90/0.48'

哪些输出

6 183 6 187.5

有人发现，随着问题规模增加六倍，执行时间增加超过 180 倍，凭经验表明复杂度为 O(n³)。 ( empirical 的发现是基于观察而不是理论。将曲线拟合到黑盒函数，其中您没有过程信息，只有输入和输出的知识，是经验性的。)

更一般地说， multiple regression 包可用于研究可能的曲线拟合函数。假设 x 是输入，y = f(x) 是观察到的输出。多元回归的思想是计算额外的输入值，例如 x²、x³、ln x、x·(ln x)、 等，然后找到最适合 y 这是输入值的线性组合。

作为一种粗略的近似，我们还可以编写一个程序来计算各种函数 g 和每个 x,y 的比率 y/g(x) 值对。以下是将此技术应用于问题中显示的数据的示例:

import math
Ns=(216,1296,7776,46656)
times=(0.00,0.48,89.73,16480.96)
for x,y in zip(Ns,times):
    print '{:5} {:8.2f} {:8.2} {:10.3} {:10.3} {:10.3} {:10.3}'.format(x, y, y/x, y/x**2, y/x**3, y/(x**2.92), y/(x**2 * math.log(x)**8))

产生

  216     0.00      0.0        0.0        0.0        0.0        0.0
 1296     0.48  0.00037   2.86e-07   2.21e-10   3.91e-10   4.11e-14
 7776    89.73    0.012   1.48e-06   1.91e-10   3.91e-10   3.58e-14
46656 16480.96     0.35   7.57e-06   1.62e-10   3.84e-10   4.24e-14

上面python程序中的最后两个函数，即g(x)=x^2.92和g(x)=x²·(ln x) ⁸，用于说明您可以测试相当复杂的函数。但请注意，这种技术有点特别。