我如何在 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 的几个值，看看是否发现了一种模式：

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²).

Answer 2

首先，计算 g() 被调用的次数，作为传递给 f() 的初始参数 n 的函数。这为您提供了该函数所花费的时间，是执行 g() 所花费时间的倍数，不包括递归。

然后舍弃系数和低阶项。例如，如果您的结果是 0.5n^2 + 0.5n，您将删除 0.5n，因为它是低阶项 - 不是平方 - 留下 0.5n^2，并且您将删除 0.5 系数，留下 n^2 .这意味着该函数在 O(n^2) 时间内运行。

Answer 3

虽然不是分析递归的一般策略，但您的 f(n) 本质上是一个循环运行ning g(k)，用于 k 的值跨越 1 到 n。所以 f(n) 的运行次本质上是 g(n), g(n-1), ..., g(2) 的运行次的总和， g(1).

由于您已经知道 g(k) 的运行时间本质上是 k，因此您最终的运行时间是从 1 到 n 的总和。如果你知道你的求和公式，你就会知道它的顺序是 O(n²).

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

How would I find the time-complexity of a recursive method in Java?

java

recursion

big-o

time-complexity