algorithm - 比较两种算法的复杂度

Question

我们有两个算法，它们在 Visual C++ 2010 中实现并且运行良好。我们知道其中的复杂度一个是n*log(n)，另一个是n^2。但是我怎样才能真正“测量”运行它们中的每一个所需的时间呢？问题是它们运行得非常快，就像几微秒一样。我能否以这种精度进行测量，或者我是否可以计算每个所需的 CPU 周期？在它们的每个循环中添加延迟是否正确？

Answer 1

好吧，如果您的输入很小，运行时间的渐近测量意味着下蹲，因为常数可能不可忽略，必须考虑在内。

大 O 表示法很有用，并且仅对大输入大小(对于 n>N 的所有输入大小对于某些常量 N)正确预测“哪种算法更好”每个算法对)。

---

要衡量这两种算法中哪一种更好，您应该尝试经验和统计方法。
(自动)生成数千(或更多)不同的测试用例，并在测试用例上运行算法。在开始运行基准测试之前不要忘记预热系统。

找出算法在每个测试用例上花费的时间(纳秒)，并使用统计方法比较两者 - 您可以查看平均时间。

您还应该运行 statistical test - 例如 Wilcoxon test找出运行时间之间的差异是否具有统计显着性。

重要提示:请注意，对于不同的机器或不同的输入分布，结果可能会有所不同 - 测试让您对特定的机器和测试用例分布有信心。