问题描述
假设我有这样的信息：
N seconds
216 0.00
1296 0.48
7776 89.73
46656 16480.96
我如何估计这个函数的增长??
How can I estimate growth of this function??
什么是经验订单-的增长？
What is the empirical order-of-growth?
我如何估计的经验订单的增长？
How can I estimate empirical order-of-growth?
任何帮助将AP preciate！
Any help will be appreciate!
推荐答案
绘制数据是一个良好的开端;如果您绘制它的线性刻度，也对数刻度，你可以从一个指数增长的功能区分多项式增长的功能。
Plotting the data is a good start; if you plot it on linear scales and also on log scales, you may be able to distinguish a polynomial-growth function from an exponential-growth function.
有关的秩序复杂性，时间的增加计算比率进行快速估计。从命令
For quick estimates of order of complexity, compute ratios of time increase. From the command
dc -e '46656 7776/ 16480.96 89.73/ 7776 1296/ 89.73 0.48/f'
它输出
186
6
183
6
或者python命令
or the python command
python -c 'print 46656/7776, 16481/90, 7776/1296, 90/0.48'
它输出
6 183 6 187.5
人们看到，作为一个因子六，通过超过180倍的执行时间的增加，经验表明一个O（n³）的复杂性问题规模的增加。 （安的 经验 的结论是基于观察而不是理论。以曲线拟合一个黑盒子的功能，那就是你有没有过程的信息，仅仅是知识的输入和输出，是经验性的。）
one sees that as the problem size increases by a factor of six, the execution time increases by a factor of over 180, empirically suggesting an O(n³) complexity. (An empirical finding is one based on observations rather than theory. Fitting a curve to a black-box function, where you have no process information, merely knowledge of inputs and outputs, is empirical.)
更一般地，一个的 多重回归的的包可被用于研究可能的曲线拟合功能。假设的 X 的是一个输入，和的 Y = F（X）的一个观察到的输出。在多元回归的想法是计算额外的输入值，例如 X 2，X 3，LN X，X·（LN X）的等，然后找到最适合的是是输入值的线性组合。
More generally, a multiple regression package may be used to study possible curve-fitting functions. Suppose x is an input, and y = f(x) an observed output. The idea in multiple regression is to compute additional input values, such as x², x³, ln x, x·(ln x), etc and then find the best fit for y that is a linear combination of the input values.
作为一个粗略的近似，一方面也可以编写一个程序，计算比率的 Y / G（x）的各种功能的先按g 的和每个的 X，Y 的值对。这里的这种技术应用到在问题中所示的数据的示例：
As a crude approximation, one can also write a program that calculates ratios y/g(x) for various functions g and for each x,y value pair. Here's an example of this technique applied to the data shown in the question:
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 和 G（X）= X 2·（LN X） ⁸的，包括说明，你可以测试相当复杂的功能。但是请注意，这种方法有点特别。
The last two functions in the above python program, ie g(x)=x and g(x)=x²·(ln x)⁸, are included to illustrate that you can test fairly complicated functions. But note that this technique is somewhat ad hoc.
这篇关于我如何估计的功能增长？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！