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

Question

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

Answer 1

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

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

---

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

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

您还应该运行统计测试- 例如Wilcoxon 测试，以确定运行时间之间的差异是否具有统计意义。

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

Answer 2

典型的“测试平台”（继承自 C）如下所示：

#define n 20
#define itera 10000000

int main(int argc, char* argv[])
{
    clock_t started;
    clock_t stopped;
    double duration;

    started = clock();

    for (unsigned long i = 0; i < itera; i++)
    {   
      for (unsigned k = 0; k < n; k++)
      {
         ....
      }
    }

    stopped = clock();

    duration = (double)(stopped - started) / CLOCKS_PER_SEC;

}

常见的陷阱：

编译器可能会优化您的代码，导致结果具有误导性。（例如，如果您分配了一个变量并且以后不使用该变量，则可能会省略计算和分配）

在执行测试时，您的系统可能正忙于其他事情。经常重复测试。

缓存效果可能会影响速度。如果磁盘访问时间起作用或涉及大量内存，则尤其如此。

算法的性能通常取决于测试数据。

测试台的外循环可能比实际算法花费更多时间。测量空循环以考虑此影响。