Java 时间复杂度 O(n^2/3)

Question

Java 时间复杂度 O(n^2/3)

6

我的数学基础不是很好，这是我尝试编写的JAVA代码，其运行时间与不同的输入成比例。

With n^2/3. Since n^2/3 = cube root n * cube root n, hence I can write

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

With 4^n. Can i use Fibonnaci method?

public int fibonnaci(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return fibonnaci(n - 2) + fibonnaci(n - 1);
    }
}

请问我的上面的代码是否正确？非常感谢！

- Gerard

1

斐波那契 - 它更接近于O(2^n)而不是O(n^4)。使用4个嵌套的for循环（从1到n递增1）作为O(n^4)的示例;-) ，而1)则是一个聪明的例子 :)

- TJ-

3个回答

1

这并不是一个真正的答案，但这里有一个“作弊”的解决方案的草图，来提供一个需要 O(F(N)) 时间的程序示例：

创建一个Java函数对象，用于计算给定 N 的 F(N) 值：
将其作为参数传递给以下方法：

   public void computeOrderFN(int n, FunctionInt2Int fn) {
      int count = fn.evaluate(n);
      for (int i = 1; i < count; i++) {
          // Do something O(1) that the compiler can't optimize away)
      }
   }

但是如果有失去“聪明鬼”的信用风险，请不要使用此功能 :-)

- Stephen C

1

你只是写任何时间复杂度为大O界限的代码吗？

那么对于#1，是的，它将需要O(n^(2/3))。

但对于#2，你的代码将需要O(2^n)和theta(1.6...^n)，其中1.6..是著名的黄金比例数。

参考资料：斐波那契数列的计算复杂度

- UGO

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bruno Reis · Accepted Answer

第一个是正确的，思路很好。

第二个不正确。计算斐波那契数列的算法时间复杂度远高于O(n^4)（编辑：当我写这篇答案时被问到了这个问题--与此同时，问题已更新）。它甚至不是多项式时间复杂度。推理如下（符号#fib(x)：计算fib(x)调用fib的次数）：

fib(1)：#fib(1) = 1（它直接返回结果）
fib(2)：#fib(2) = 3（其中一个为fib(2)，它分别调用fib(0)和fib(1)）
fib(3)：#fib(3) = 5（其中一个为fib(3)，它分别调用fib(2)和fib(1)，再加上3 + 1次调用）
fib(4)：#fib(4) = 9
fib(5)：#fib(5) = 15
fib(6)：#fib(6) = 25
...
fib(i)：#fib(i) = 1 + #fib(i-1) + #fib(i-2)

因此，你有：

#fib(i) ~= #fib(i-1) + #fib(i-2)

由此可以猜测，计算fib(i)需要的时间是计算fib(i-1)时间的"大约"2倍（实际上略少于2倍）。因此，你可以"猜测"O(#fib(i)) = O(2^i)。这是正确的答案，你可以通过归纳证明它。

最后说一下斐波那契数列。有更快的算法来计算第n个数字。例如，一个线性时间复杂度（即O(n)）的算法是对这个函数进行记忆化（即，使其查询Map以检查是否知道n的结果，如果是，则立即返回它，否则，计算它，存储它并返回它）。还有一个计算第n个斐波那契数的闭式公式，因此是一个常量时间复杂度算法（即O(1)）。

最后，一个O(n^4)算法的例子就是任何内部有4个循环的算法，每个循环运行"大约"n次。

例如，计算n个边长为n的立方体的体积（非最优方式）：

int volume = 0;
for (int cube = 0; cube < n; cube++)
  for (int x = 0; x < n; x++)
    for (int y = 0; y < n; y++)
      for (int z = 0; z < n; z++)
        volume++;
return volume;