9

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

4

6 回答 6

11

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

您首先要猜测算法的理论复杂度函数。对于越来越大的问题，您还可以通过实验测量实际复杂性（操作数量、时间或任何您认为实用的东西）。

例如，假设您猜测算法是二次的。测量（说）时间，并计算时间与您猜测的函数的比率（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。

于 2010-10-21T00:33:19.933 回答
6

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

算法执行的操作数作为其输入大小的函数。

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

这会给你一个很好的“理论”估计。
另一方面，如果您想要真实的数字，请使用profiling。

于 2010-10-20T19:15:00.643 回答
2

正如其他人所提到的，理论时间复杂度是算法完成的 CPU 操作数量的函数。一般来说，处理器时间应该是模常数的一个很好的近似值。但实际运行时间可能会因多种原因而有所不同，例如：

  1. 处理器管道刷新
  2. 缓存未命中
  3. 垃圾收集
  4. 机器上的其他进程

除非您的代码系统地导致其中一些事情发生，否则有足够数量的统计样本，您应该根据观察到的运行时间对算法的时间复杂度有一个相当好的了解。

于 2010-10-21T04:11:52.963 回答
1

最好的方法是实际计算算法执行的“操作”数量。“运算”的定义可能会有所不同：对于快速排序等算法，它可能是两个数字的比较次数。

您可以测量程序花费的时间以获得粗略估计，但各种因素可能导致该值与实际的数学复杂性不同。

于 2010-10-20T19:18:18.610 回答
0

是的。

您可以同时跟踪实际性能和迭代次数。

于 2010-10-20T19:14:42.110 回答
0

我可以建议使用 ANTS 分析器吗？当您使用“实验”数据运行应用程序时，它将为您提供此类详细信息。

于 2010-10-20T19:17:30.717 回答