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

发布时间：2020-12-14 05:59:11 所属栏目：Java 来源：网络整理

导读：我无法完全掌握复杂性的概念,我想知道如何在这段代码中为方法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

我无法完全掌握复杂性的概念,我想知道如何在这段代码中为方法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.我不知道从哪里开始任何帮助都会很棒.谢谢.

解决方法

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

> c0 = 1(调用g(0)需要一定量的工作)
> cn 1 = cn 1(调用g(n)执行一定量的自己的工作,然后调用g(n-1)

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

> c0 = 1
> c1 = c0 1 = 1 1 = 2
> c2 = c1 1 = 2 1 = 3
> c3 = c2 1 = 3 1 = 4

一般来说,它看起来像cn = n 1.如果您愿意,您可以通过归纳证明来形式化这一点,但是现在我们将依据它来接受它.这意味着g的运行时间是O(n).

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

> d0 = 1(调用f(0)执行一定量的工作)
> dn 1 = dn cn 1(调用f(n 1)调用g(n 1),需要cn 1工作,然后调用f(n)

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

> d0 = 1
> d1 = c1 d0 = 2 1
> d2 = c2 d1 = 3 2 1
> d3 = c3 d2 = 4 3 2 1

一般来说,它看起来像dn = n(n-1)(n-2)…… 1.如果你愿意,你可以通过归纳形式化它.这是一个着名的和,它适用于n(n 1)/ 2.这个量碰巧是Θ(n2),所以整个运行时间是Θ(n2).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!