0

当我看到一个算法时，我了解如何找到算法的时间复杂度，但是当我得到算法的次数时，我似乎无法弄清楚如何计算它执行，以及花费的时间。

我有时可以得到它，当它很明显像 O(n)、O(n) 或 O(n^2) 时，但以这个问题为例：

算法运行大小为 n 的给定输入。如果 n 为 4096，则运行时间为 512 毫秒。如果 n 为 16384，则运行时间为 1024 毫秒。如果 n 为 36864，则运行时间为 1536 毫秒。

时间复杂度是多少？

我认为它是 n * 2, t * 1.5，但我不太确定如何计算出来。

谢谢您的帮助 ：）

4

3 回答 3

2

我会说对于这类问题，您需要的不仅仅是三个数据点，因为系统的复杂性而不仅仅是算法。

我要做的是比较迭代和经过的时间，看看是否能找到与标准时间复杂度之一匹配的模式：

  • 常数：O(c)，其中 c 是常数。
  • 线性：O(n)
  • 多项式：O(n^c) 其中 c 是一个常数（或者甚至像 O(n^2 + n^6) 这样复杂的东西）
  • 指数：O(c^n) 其中 c 是一个常数。
  • 对数：O(log|n|)
  • 不管这叫什么：O(n log|n|)

让我们来看看你的问题：

n     | time
4096  | 512 ms
16384 | 1024 ms
36864 | 1536 ms

当 n 增加 4 倍（从 4096 到 16384）时，时间增加 2 倍（从 512 到 1024 毫秒）。

当 n 增加 9 倍（从 4096 到 36864）时，时间增加 3 倍（从 512 到 1536 毫秒）。

与此匹配的函数是 f(n) = n^(1/2)。当 n 上升 4 倍时，f(n) 上升 sqrt(4) 倍，等等......

所以这是 O(n^.5) 阶，它是多项式

TLDR：将其绘制成图表并将其与时间复杂度的常用函数相匹配。在现实世界中，您可能需要三个以上的数据点。

编辑：我想补充一点，这应该更复杂。每种时间复杂度都可能有一个常数项。即 O(n^c) 更可能是 O(n^c + K)，其中 K 是常数。写出来时，为了简单起见，我们忽略了常数，但它会显示在您的图表中。

于 2012-10-13T22:54:29.947 回答
0

如果您不确定实际的算法，那么您将创建一个折线图，n位于图的底部，并且y将是执行该数字所花费的时间。

如果直线的斜率为 0，那么它是 O(1)，如果它是线性的，那么它是 O(n)，如果它是弯曲的，那么它是 O(n^2)、O(log n) 或其他一些非线性时间复杂度。

于 2012-10-13T22:46:27.840 回答
0

如果一个算法的时间复杂度是n^x，那么t_2 / t_1输入n_1和的时间的商n_2是

(t_2 / t_1) = (n_2 / n_1)^x

如果你取对数，你会得到

log (t_2 / t_1) = x * log (n_2 / n_1)

并且可以解决x：

x = log (t_2 / t_1) / log (n_2 / n_1)

在您的示例中，使用n_1 = 4096and t_1 = 512ms，您可以得到商

16384 / 4096 = 4        36864 / 4096 = 9
 1024 / 512  = 2         1536 / 512  = 3

所以x = 1/2。

如果复杂性不遵循纯幂律，您可以通过评估足够多的此类商来估计幂。如果复杂度实际上是指数（或超指数），则商将线性或超线性增长。然后可以使用增长率来找到指数情况下指数的基数。

于 2012-10-13T22:49:26.620 回答