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

Question

我的数学背景不太好，这是我尝试编写具有运行时比例的不同输入的 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);
       }
   }
   

我可以知道我上面的代码是否正确吗？非常感谢!

Answer 1

第一个是正确的，而且经过深思熟虑。

---

第二个不是。计算 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) 所花费的时间是计算 fib(i-1) 的“大约”(实际上，只是略小于)2 倍。因此，您可以“猜测”O(#fib(i)) = O(2^i)。这是正确答案，您可以通过归纳法轻松证明。

为了完成斐波那契数列，有更快的算法来计算第 n 个数。例如，具有线性时间(即 O(n))的算法是记住您编写的函数(即，让它查询 Map 以检查它是否知道 n 的结果，因此立即返回它，否则，计算它，存储它并返回它)。还有一个 closed formula to calculate the n-th 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;