6

我的数学背景不太好，这是我尝试编写运行时与不同输入比例的 JAVA 代码。

  1. 用 n^2/3。由于 n^2/3 = 立方根 n * 立方根 n，因此我可以写

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

  2. 用 4^n。我可以使用斐波那契方法吗？

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

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

4

3 回答 3

5

第一个是正确的，而且考虑得很周到。

第二个不是。计算 fibs 的算法具有比 O(n^4) 高得多的时间复杂度（编辑：这是我写这个答案时被问到的——同时问题已经更新）。它甚至不是多项式。推理如下（符号#fib(x)：调用fib计算fib(x)的次数）：

  • 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) 需要“大约”（实际上，略少于）2 倍于计算 fib(i-1) 的时间。因此，您可以“猜测” O(#fib(i)) = O(2^i)。这是正确的答案，您可以通过归纳轻松证明。

只是为了完成斐波那契数列，有更快的算法来计算第 n 个数。例如，具有线性时间（即 O(n)）的算法是要记住您编写的那个函数（即，让它参考​​ Map 以检查它是否知道 n 的结果，所以立即返回它，否则，计算它，存储它并返回它）。还有一个封闭的公式来计算第 n 个 fib，因此是一个恒定时间算法（即 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;
于 2012-10-14T06:10:12.577 回答
1

您是否只是在编写任何需要时间复杂度的大 O 界限的代码？

比#1，是的，它需要O(n^(2/3)).

但是对于＃2，您的代码将采用O(2^n), 和theta(1.6...^n), 和 1.6.. 是著名的黄金比例数。

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

于 2012-10-14T06:01:47.540 回答
1

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

  1. 创建一个 Java 函数对象来评估F(N)给定的N:

  2. 将其作为参数传递给以下方法：

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

但是，如果有可能因为“聪明**”而失去信誉，请不要使用它:-)

于 2012-10-14T06:31:51.310 回答