algorithm - 根据样本运行估算模拟运行时间

Question

我需要在周末运行一次模拟。我希望模拟足够大，尽可能具有描述性，但我不希望它在我回去工作时还没有完成，我无法继续使用该软件。

该算法一旦开始，就必须完成，否则根本没有运行它的意义。

模拟的各个元素以阶乘、n^4 和 n^2 的形式运行

   n:
<= 6  =         0ms
   7  =         8ms
   8  =        91ms
   9  =     1,089ms
   10 =    14,666ms
   11 =   197,288ms
   12 = 3,091,739ms

我在 WolframAlpha 中为这些样本拟合了一条曲线 here .让我担心的两件事首先是 n^4 分量是负数，这没有任何意义，因为它肯定是影响运行时的一个因素。另一件事是，我曾尝试估计过去类似情况下的运行时间，但我的推断通常有很大偏差。

你们有没有以这种方式根据输入大小猜测算法运行时间的经验？

Answer 1

一般来说，当您有一些 O(N⁴) 时，您还必须引入 O(N³)、O(N²)、O(N) 和 O(1)。换句话说，尝试将 x³、x¹ 和 x⁰ 添加到曲线拟合模型中。

对于这个复杂度为 O(N!) 的特殊情况，好吧，我会遵循我的建议，只考虑阶乘部分，因为它似乎收敛得相当快。

但无论如何，如果你真的有一个 O(N!) 你不需要估计，只需使用一个 iterative deepening方法。让您的计算机迭代运行 n=1,2,3,4,5,6,7... 的情况，并尽可能地进行下去。

看起来你在浪费你的计算机时间，但如果你分析一下，你会发现浪费的时间是微不足道的。例如，您已经在 n=12，因此对于 n=13，所需的 CPU C₁₃ 将是 13*C₁₂，C₁₂ = 12*C₁₁ 等等。引入您的测量值，sum(C₁₃..C₀)/C₁₃ = 1.082，因此针对从 0 开始的所有值运行您的函数到 13 只比运行它 13 的成本高 8%。当你追求更大的 N 值时，这个百分比将进一步降低。

更新:

为什么需要为复杂度以下的所有幂添加项:

考虑一个复杂度为 O(N₃) 的简单三级循环:

void foo(int n) {
  int i, j, k;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      for (k = 0; k < n; k++)
        do_something(i, j, k);
}

foo(3);

很明显 do_something(i, j, k)被调用 n³ 次。

但如果我们从头开始考虑执行的每条指令，我们可以看到比进入和离开函数、设置堆栈和其他低级任务一次完成； i=0指令也执行一次。这些是对应于 n⁰ 成本的指令。

说明i < n , i++和 j=0被调用n次，对应n¹项。

说明j < n , j++和 k=0被调用n²次，对应n²项。

嗯，等等。

更复杂的情况是相同的，您总是有指令运行的次数与复杂性级别以下的所有幂成正比。

关于你测量C(0) = 0 ，这只是你的时间不够准确的问题。它可能非常小，但绝不是绝对的 0。

最后，如果您的曲线拟合不起作用，那是因为 N!在那种情况下，您还将有指令运行(n-1)!次，以及 (n-2!) 次等等。