这是一个复杂度为O(4 ^ n)的算法?

I am given a question to write a method with a time complexity of O(4^n).

我给一个问题写一个方法的时间复杂度O(4 ^ n)。

I have came out with this algorithm:

我提出了这个算法:

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

Is this be considered to be running on O(4^n)?

这是被认为是运行在O(4 ^ n)?

4 个解决方案

#1

You were quite close with your program. The correct function would go like this:

你和你的程序很接近。正确的函数是这样的:

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

Run this piece of code to check:

运行这段代码检查:

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);
  }
}

It will print

它将打印

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

The run count is off by one, but the big-O complexity is satisfied.

运行计数减少了一个，但是大o复杂度得到了满足。

The reasoning as to why it is O(4ⁿ) is probably quite obvious once you see it, but a little explanation cannot hurt. The function is best imagined to be solving a complex problem by divide-and-conquer. It reduces an n-sized problem to four instances of an (n-1)-sized problem, recursing until the subproblem is trivial (size 0). A problem of size 1 is therefore solved in 1+4 steps (entry-point call + 4 trivial subproblems); a problem of size 2 in 1 + 4*(1 + 4) = 21 steps, and so on.

关于为什么它是O(4n)的推理很明显，一旦你看到它，但一点解释也无妨。这个函数最好是通过分治来解决一个复杂的问题。它将n大小的问题简化为(n-1)大小的问题的四个实例，递归到子问题变得微不足道(大小为0)。1 + 4*(1 + 4) = 21步，以此类推。

#2

No, it isn't.

不,它不是。

Calling test(0) will return immediately. So will calling test with a negative number.

调用test(0)将立即返回。用负数调用test也一样。

Calling test with a positive number will never return (it will with overflow, but that's something you don't usually take into account when calculating complexity).

用正数调用测试将永远不会返回(它将带溢出，但是在计算复杂性时通常不考虑这一点)。

#3

No it is not. This program will run infinitely for number greater than 1. Hence its not of O(4^n)

不,它不是。这个程序对大于1的数无限运行。因此它不是O(4 ^ n)

#4

As it has been said, that will run forever for a given input greater than 1. To write a 4^n complexity program, try to think about an operation which gets 4 times more complex for n than for n-1. For instance dividing a square in 4 smaller squares for n = 1, and then dividing those squares again for n = 2...

如前所述，当输入大于1时，它将永远运行。写4 ^ n复杂程序,试着去思考一个操作,4倍更复杂的比n - 1 n。例如，把一个正方形分成4个小的正方形，n = 1，然后再把这些正方形分成4个小的正方形，n = 2……

You will realize that the number of squares will be 4^n as so will the time complexity of the algorithm.

你会意识到广场的数量将4 ^ n将算法的时间复杂度。

Understand however that the big o notation represents an upper bound, so any operation which is O(n) will also be O(4^n) but I guess that's not what's intended...

理解但是大o符号代表一个上界,所以任何操作是o(n)也将o(4 ^ n),但我想这不是什么目的…

#1