当前位置：文江博客话题详情

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

发布于 2024-09-28 01:19:15 字数 50 浏览 1 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

平安喜乐 2024-10-05 01:19:15

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

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

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

The currently accepted won't give you any theoretical estimation, unless you are somehow able to fit the experimentally measured times with a function that approximates them. This answer gives you a manual technique to do that and fills that gap.

You start by guessing the theoretical complexity function of the algorithm. You also experimentally measure the actual complexity (number of operations, time, or whatever you find practical), for increasingly larger problems.

For example, say you guess an algorithm is quadratic. Measure (Say) the time, and compute the ratio of time to your guessed function (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

. As n moves towards infinity, this ratio...

Converges to zero? Then your guess is too low. Repeat with something bigger (e.g. n^3)
Diverges to infinity? Then your guess is too high. Repeat with something smaller (e.g. nlogn)
Converges to a positive constant? Bingo! Your guess is on the money (at least approximates the theoretical complexity for as large n values as you tried)

Basically that uses the definition of big O notation, that f(x) = O(g(x)) <=> f(x) < c * g(x) - f(x) is the actual cost of your algorithm, g(x) is the guess you put, and c is a constant. So basically you try to experimentally find the limit of f(x)/g(x); if your guess hits the real complexity, this ratio will estimate the constant c.

回复收藏 0 原文