4

我需要在一个周末运行一次模拟。我希望模拟足够大，使其尽可能具有描述性，但我不希望它在我重新开始工作时还没有完成，我不能继续使用这个软件。

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

模拟的各个元素以阶乘、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 中为这些样本拟合了一条曲线。我关心的两件事首先是 n^4 分量是负数，这没有任何意义，因为它肯定是运行时的一个促成因素。另一件事是，我过去曾尝试在类似情况下估计运行时间，而我的推断通常很遥远。

你们中是否有人以这种方式根据输入大小猜测算法的运行时间？

4

2 回答 2

1

外推失败的原因：
当您要估计原始范围之外的值时，预计外推会很远。
至少在多项式外推中 -误差是点到所有样本点之间的距离的乘积，以及函数在该范围内的第 n 阶导数的最大值的函数。如果这个距离很大 - 它（距离和最大导数的乘积）预计会很高。

n^4 分量给出负值，因为它显示了可以解释“观察”的最佳函数。

为了估计样本区域之外的运行时间 - 我建议避免使用外推法。当走出已知样本的“舒适区”时，根据定义，它们不是很好的估计。

考虑一个替代方案：
我会尝试找到常量的粗略估计（通过静态分析代码） - 主要是 - 我想看看阶乘分量是否有非常小的常数，而其余的有非常大的常数。如果不是这种情况，则可以忽略 n^2 和 n^4 分量 - 与阶乘分量相比，它们可以忽略不计，这将更容易分析。

PS从您提供的动态数据来看 - 似乎是这样，运行时间之间的差异正在迅速收敛到阶乘因素，因此将函数分析为阶乘和估计f(12) ~= 12* f(11)等似乎是一个合理的假设。
如果您想安全起见，可以使用f(n) = (n + d) * f(n-1)，其中 d 是预定义的正常数，例如d = max{0,f(11)/f(10) - 11}。

PS2：
由于阶乘的行为如此激进，您可以尝试迭代地运行模拟，f(1) + f(2) + ... + f(n)预计不会花费太多f(n)时间n > 10。通过这样做，您将获得您有时间计算的结果，尽管您在回到办公室时中止了它。这种行为被称为任何时候。

于 2012-06-21T06:09:43.210 回答
1

一般来说，当你有一些 O(N 4 ) 时，你还必须引入 O(N 3 )、O(N 2 )、O(N) 和 O(1) 的术语。换句话说，尝试将 x 3、 x 1和 x 0添加到曲线拟合模型中。

对于这种特殊情况，你有一个 O(N!)，好吧，我会遵循 amit 的建议，只考虑阶乘部分，因为它似乎收敛得很快。

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

看起来你在浪费你的计算机时间，但如果你分析它，你会发现浪费的时间是微不足道的。例如，您已经在 n=12，因此对于 n=13，所需的 CPU C 13将是 13*C 12、 C 12 = 12*C 11等等。介绍您的测量值 sum(C 13 ..C 0 )/C 13 = 1.082，因此对从 0 到 13 的所有值运行函数仅比运行 13 贵 8%。 N 值越大，该百分比将进一步降低。

更新：

为什么您需要为复杂性级别以下的所有幂添加项：

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

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 3次。

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

指令i < n和被调用 n 次i++，j=0它们对应于 n 1项。

指令j < n和被调用 n 2j++次，它们对应于 n 2项。k=0

嗯，等等。

更复杂的情况是一样的，你总是有指令运行的次数与低于复杂性级别的所有幂成正比。

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

最后，如果你的曲线拟合不起作用，那是因为 N! 在这种情况下，您还将运行指令（n-1）！次，和（n-2！）次等等。

于 2012-06-21T07:04:41.833 回答