如何在Java中找到递归方法的时间复杂度？

Question

我无法完全掌握复杂性的概念,我想知道如何在这段代码中为方法f(n)计算它:

import java.util.Random;

public class Main {
  public static void main(String[] args) {
    Random r = new Random();
    r.setSeed(System.currentTimeMillis());
    int n = r.nextInt(20) + 1;
    f(n);
  }

  private static void f(int n){
    if(n > 0){
      g(n);
      System.out.println();
      f(n-1);
    }
  }

  private static void g(int n){
    if(n > 0){
      System.out.print('X');
      g(n-1);
    }
  }
}

我知道这是一种递归方法,令我感到困惑.我看到每次调用函数f()时,都会调用g()并运行n次,然后f()再次将自身称为n-1,直到n = 0.我不知道从哪里开始任何帮助都会很棒.谢谢.

Answer 1

确定递归函数的运行时间的常用技术是写出将运行时描述为根据其自身定义的数量的递归关系.让我们从g开始.如果我们让c _n表示g(n)的运行时间,那么我们就有了

• c ₀ = 1(调用g(0)需要一定量的工作)
• c _{n + 1} = c _n + 1(调用g(n)执行一定量的自己的工作,然后调用g(n-1)

我们可以查看几个值来查看我们是否发现了一个模式:

• c ₀ = 1
• c ₁ = c ₀ + 1 = 1 + 1 = 2
• c ₂ = c ₁ + 1 = 2 + 1 = 3
• c ₃ = c ₂ + 1 = 3 + 1 = 4

一般来说,它看起来像c _n = n + 1.如果你愿意的话,可以通过归纳证明来形式化这个,但是现在我们要坚信它.这意味着g的运行时间是O(n).

现在,让我们让d _n成为调用f(n)的运行时.请注意

• d ₀ = 1(调用f(0)做一定量的工作)
• d _{n + 1} = d _n + c _{n + 1}(调用f(n + 1)调用g(n + 1),需要c _{n + 1}工作,然后调用f(n)

我们可以扩展它,看看我们是否看到了一种模式.

• d ₀ = 1
• d ₁ = c ₁ + d ₀ = 2 + 1
• d ₂ = c ₂ + d ₁ = 3 + 2 + 1
• d ₃ = c ₃ + d ₂ = 4 + 3 + 2 + 1

通常,它看起来像d _n = n +(n-1)+(n-2)+ ... + 1.如果您愿意,可以通过归纳将其形式化.这是一个着名的和,它可以达到n(n + 1)/ 2.这个数量碰巧是Θ(n ²),所以整个运行时间是Θ(n ²).