algorithm - 如何测试时间复杂度 "experimentally"？

Question

是否可以通过保留一个计数器来查看算法经过了多少次迭代来完成，或者是否需要记录持续时间？

Answer 1

目前接受的不会给你任何理论估计，除非你能以某种方式用一个近似它们的函数来拟合实验测量的时间。这个答案为您提供了一种手动技术来执行此操作并填补了这一空白。

您首先猜测算法的理论复杂度函数。您还可以通过实验测量越来越大的问题的实际复杂性(操作数、时间或您认为可行的任何因素)。

例如，假设您猜测算法是二次的。测量(说)时间，并计算时间与您猜测的函数 (n^2) 的比率:

for n = 5 to 10000 //n: problem size
  long start = System.time()
  executeAlgorithm(n)
  long end = System.time()
  long totalTime = end - start

  double ratio = (double) time / (n * n)
end

.作为n向无穷大移动，这个比例...

• 收敛于零？那你的猜测就太低了。用更大的东西重复(例如 n^3)
• 发散到无穷大？那你的猜测就太高了。用更小的东西重复(例如 nlogn)
• 收敛于正常数？答对了!您的猜测是对的(至少近似于与您尝试的一样大的 n 值的理论复杂性)

基本上使用大 O 符号的定义，即 f(x) = O(g(x)) <=> f(x) < c * g(x) - f(x)是算法的实际成本，g(x)是你的猜测，c是一个常数。所以基本上你尝试通过实验找到 f(x)/g(x) 的极限;如果你的猜测达到了真正的复杂性，这个比率将估计常量 c .