比较两种算法的复杂性
我们有两个在Visual C ++ 2010中实现的算法，并且工作正常。 我们知道其中的一个是n * log（n），另一个是n ^ 2。 但是，我怎么能“测量”每个人运行所需的时间呢？ 问题在于它们运行得非常快，就像几秒钟。 我能以这种精度进行测量，还是可以计算每个CPU所需的CPU周期？ 在每个循环中添加延迟是正确的？
那么，如果你的输入很小，运行时间的渐近测量就意味着下蹲，因为这个常数可能不可忽略，并且必须加以考虑。
大O符号是有用的，并且只有对于大输入大小（对于n>N所有输入大小，对于每个算法对的某个常数N ），才能正确预测“哪种算法更好”。
为了测量两种算法哪一种更好，你应该尝试经验和统计方法。
生成数千（或更多）不同的测试用例（自动），并在测试用例上运行算法。 在开始运行基准测试之前，不要忘记预热系统。
找出每个测试用例所用算法的时间（纳秒），并使用统计度量比较两者 - 您可以查看平均时间。
您还应该运行统计测试 - 例如Wilcoxon测试，以确定运行时间之间的差异是否具有统计学意义。
重要提示：请注意，对于不同的机器或不同的输入分配，结果可能会有所不同 - 测试可让您对特定机器和测试用例分配充满信心。
一个典型的“测试床”（从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;
}
频繁的陷阱：
编译器可能会以使结果具有误导性的方式优化代码。 （例如，如果您分配了一个变量并且稍后不使用该变量，那么计算和分配可能会被省略）
执行测试时，您的系统可能忙于其他事情。 重复测试足够频繁。
缓存效果可能会影响速度。 如果磁盘访问时间起作用或涉及大量内存，情况尤其如此。
算法的性能通常取决于测试数据。
测试平台的外部循环可能需要比实际算法更多的时间。 测量空循环以考虑此影响。
链接地址: http://www.djcxy.com/p/40073.html