算法的实验分析 - 如何证明图形是 O(nlogn)？
Experimental Analysis of an Algorithm - How to prove that the graph is O(nlogn)?
这个问题可能很愚蠢，但我已经尝试解决这个问题好几个小时了，但我仍然找不到任何相关信息。可能是我太迷路了。
基本上，我是通过渐近和实验分析来分析算法的。渐近分析进行得很顺利，我得出结论，我的算法是 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 log n)/线性算术图，但我如何证明它？我必须计算增长顺序吗？如果可以，我该怎么做？
感谢您的帮助！
根据输入大小绘制时间。
曲线拟合该图的 y=A*n*log(n) + B 曲线，通过创建该曲线与实验绘图之间关系的最小均方拟合来求解 A 和 B。
对代表 O(n) 和 O(n^2) 的线性曲线（一条线）执行相同的操作。表明其他曲线的拟合比 O(n*log(n)) 曲线有更多误差。
如果一条曲线的拟合误差较低，则您收集的数据支持该曲线以大 O 表示法增长。
这个问题可能很愚蠢，但我已经尝试解决这个问题好几个小时了，但我仍然找不到任何相关信息。可能是我太迷路了。
基本上，我是通过渐近和实验分析来分析算法的。渐近分析进行得很顺利，我得出结论，我的算法是 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 log n)/线性算术图，但我如何证明它？我必须计算增长顺序吗？如果可以，我该怎么做？
感谢您的帮助！
根据输入大小绘制时间。
曲线拟合该图的 y=A*n*log(n) + B 曲线，通过创建该曲线与实验绘图之间关系的最小均方拟合来求解 A 和 B。
对代表 O(n) 和 O(n^2) 的线性曲线（一条线）执行相同的操作。表明其他曲线的拟合比 O(n*log(n)) 曲线有更多误差。
如果一条曲线的拟合误差较低，则您收集的数据支持该曲线以大 O 表示法增长。