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.我可以使用Fibonnaci方法吗？

   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)需要2倍于计算fib(i-1)的时间(实际上,稍微小一点).因此,你可以"猜测"O(#fib(i))= O(2 ^ i).这是正确答案,您可以通过归纳轻松证明.

只是为了完成Fibonacci序列,有更快的算法来计算第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;

Answer 2

您是否正在编写任何需要大范围时间复杂度的代码？

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

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

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