图的差异和渐近分析比较算法的运行时间

Question

这个问题几乎说明了我的要求.

我有一个算法,我在徘徊什么是更好的方法来实现啊'大哦'运行时间 - 通过图表和绘制输入的数量与运行时间,或通过渐近分析？

对于我目前正在使用的图表:

private int startTime = System.currentTimeMillis(); //At start of algorithm
private int endTime = System.currentTimeMillis(); //At the end of algorithm
int runningTime = endTime - startTime;

两种"测量"算法运行时间的方法有什么区别？

Answer 1

“经验”的问题（根据输入大小绘制运行时间）是否仅适用于提供的测试用例。

“理论”分析为您提供了算法的所有陷阱，您可以使用数学分析真正的最佳情况/平均情况/...，并且保证是正确的。

一个很好的常见例子是单纯形算法，它通常非常快，但对于某些输入偶尔会出现指数最坏情况的运行时间。

另一方面，由于渐近分析忽略常数，并且仅适用于“足够大的输入”，如果输入预计相对较小，则它们几乎没有用处，并且很难区分相同复杂度的两种算法类，但具有不同的常量，并且常量在生产代码中确实很重要。

tl;dr：每种都有自己的用法，将两者结合起来比仅使用其中一种效果更好。

顺便说一句，在使用实证方法时，一定要使用统计工具，并在做出结论之前专门进行统计假设检验。另外，请始终记住，经验工具仅对您检查的问题类别有效（因此，如果您不检查排序数组，您将不知道快速排序在遇到排序数组时可能会花费更长的时间）。