2

我被要求编写一个时间复杂度为 O(4^n) 的方法。

我提出了这个算法：

public void test(int n){
   for(int i = 0; i<n;i++){
      test(4*i);
   }
}

这是否被认为在 O(4^n) 上运行？

4

4 回答 4

3

不，不是。

调用 test(0) 将立即返回。用负数调用测试也是如此。

用正数调用 test 将永远不会返回（它会溢出，但在计算复杂度时通常不会考虑这一点）。

于 2012-10-14T12:01:51.400 回答
3

你非常接近你的程序。正确的功能应该是这样的：

public void test(int n) {
  if (n == 0) return;
  for (int i = 0; i < 4; i++) test(n-1);
}

运行这段代码来检查：

static int runs;
static void test(int n) {
  runs++;
  if (n == 0) return;
  for (int i = 0; i < 4; i++) test(n-1);
}
public static void main(String[] args) {
  for (int n = 1; n <= 5; n++) {
    runs = 0;
    test(n);
    System.out.format("%d: %d %d\n", n, 1<<(2*n), runs);
  }
}

它会打印

1: 4 5
2: 16 21
3: 64 85
4: 256 341
5: 1024 1365

运行计数减一，但满足大 O 复杂性。

一旦你看到它，为什么它是 O(4 n ) 的原因可能很明显，但一点解释也不会伤害到它。最好把这个功能想象成通过分而治之的方式解决一个复杂的问题。它将一个 n 大小的问题减少为一个 ( n-1 ) 大小的问题的四个实例，递归直到子问题是微不足道的（大小为 0）。因此，大小为 1 的问题在 1+4 步中得到解决（入口点调用 + 4 个普通子问题）；1 + 4*(1 + 4) = 21 步中大小为 2 的问题，依此类推。

于 2012-10-14T12:35:10.260 回答
1

不它不是。对于大于 1 的数字，该程序将无限运行。因此它不是 O(4^n)

于 2012-10-14T12:05:07.113 回答
1

正如已经说过的，对于大于 1 的给定输入，这将永远运行。要编写一个 4^n 复杂度的程序，请尝试考虑一个运算，它对于 n 比对于 n-1 复杂 4 倍。例如，将一个正方形分成 4 个较小的正方形以获得 n = 1，然后再将这些正方形划分为 n = 2 ...

您将意识到正方形的数量将是 4^n，算法的时间复杂度也是如此。

然而，请理解大 o 符号表示一个上限，因此任何 O(n) 的操作也将是 O(4^n) 但我想这不是预期的......

于 2012-10-14T12:16:05.990 回答