方法的复杂性分析

Question

需要分析递归函数的复杂度。函数如下

int hello(int n){
   if(n==0)
       return 0;
   for(int i=0;i<n;i++){
      for(int j=0;j<n * n;j++){
         System.out.println("HELLO");
      }
   }
   return hello(n-1);
}

我迷茫的步骤是hello(n-1)。我不知道如何评估像该代码这样的复杂性。如果你一步一步地告诉这个问题的解决方案，我将不胜感激。提前致谢。

Answer 1

设递归函数的运行ning 时间用 T(n) 表示，其中 n 是输入的大小。在递归关系中，输入大小为 n 的递归函数的运行ning 时间用 n 的较低值的运行ning 时间表示。你的情况

T(n) = T(n-1) + n^3（嵌套循环运行 for O(n^3)）

= T(n-2) + (n-1)^3 + n^3

= T(n-3) + (n-2)^3 + (n-1)^3 + n^3

..... ...... .......

= T(0) + 1^3 + 2^3 + 3^3 + ...... + (n-2)^3 + (n-1)^3 + n^3

= 1^3 + 2^3 + 3^3 + ....... + (n-2)^3 + (n-1)^3 + n^3

=

= O(n^4)

我们可以知道它的复杂度为 O(n^4)，因为一旦我们解决了它，我们将忽略方程中所有具有较低指数的常数和变量，而 n^4 将是 n 的最高次方。

以防万一你听说过求解递推关系的大定理。并想知道如何使用它来查找这种情况的时间复杂度。你不能，因为它不是 T(n) = a*T(n/b) + f(n).

的形式

如果您能够以某种方式将其转换为那种形式，它可能会起作用。不是最好的选择，因为我们已经有众所周知的身份可以在这种情况下使用。 Master Theorem 是一个工具而不是负担，尽可能使用它，否则使用最适合的方法。

方法的复杂性分析

Complexity analysis of a method

recursion

complexity-theory