如何通过"实验"测试时间复杂度？

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.

Answer 2

算法复杂度定义为（类似：）

算法执行的操作次数取决于其输入大小。

因此，您需要尝试使用各种输入大小的算法（例如，排序-尝试对10个元素，100个元素等进行排序），并对算法执行的每个运算（例如，赋值，增量，数学运算等）进行计数。

这将为您提供良好的“理论”估计。
另一方面，如果您需要真实的数字，请使用分析。