一个算法的实验分析--如何证明图是O(nlogn)？

Question

这个问题可能很愚蠢，但我已经尝试了几个小时，但我仍然找不到任何关于它的东西。也许我只是太迷茫了。

所以基本上，我是通过渐近和实验分析来分析算法的。渐近分析进行得很好，我得出结论，我的算法是O(nlogn)。问题在于实验分析。首先，我做了一些测试，以获得每次输入所需的时间。例如：

N= 1，t=0|n= 2，t=2|n= 4，t=8|n= 8，t= 24 |n= 16，t= 64 |n= 32，t= 160 (...)

如果我用这个例子做这个图，我可以看到它是一个O( n )/linearithmetic图，但是我如何证明它呢？我需要计算增长的顺序吗？如果是这样，我该怎么做呢？

谢谢你的帮助！

Answer 1

根据输入大小绘制时间。

曲线将y=A*n*log(n) + B曲线拟合到该曲线，通过创建该曲线与实验绘图之间关系的最小均方拟合来求解A和B。

对表示O(n)的线性曲线(直线)和O(n^2)执行相同的操作。结果表明，与O(n*log(n))曲线相比，其它曲线的拟合误差更大。

如果一条曲线的拟合误差较低，则您收集的数据支持该曲线以大O表示法增长。