7

我在这里有两个不同的递归函数，用于在 Java 中反转字符串：

    Long ms1 = System.currentTimeMillis();
    String str1 = reverse1(str);
    ms1 = System.currentTimeMillis() - ms1;

    Long ms2 = System.currentTimeMillis();
    String str2 = reverse2(str);
    ms2 = System.currentTimeMillis() - ms2;

    System.out.println("Input: " + str);
    System.out.println("  Length: " + str.length());
    System.out.println("Reverse 1:");
    System.out.println("  " + herp + " function calls");
    System.out.println("  " + ms1 +  " milliseconds");
    System.out.println("Reverse 2:");
    System.out.println("  " + derp + " function calls");
    System.out.println("  " + ms2 +  " milliseconds");
}
public static String reverse1(String str){
    herp++;
    if(str.length() == 1) return str;
    return reverse1(str.substring(str.length()/2)) + reverse1(str.substring(0, str.length()/2));
}
public static String reverse2(String str){
    derp++;
    if(str.length() == 1) return str;
    return reverse2(str.substring(1)) + str.charAt(0);
}

给定一个长度为 5000 的字符串，这是程序的输出：

Input: ...
  Length: 5000
Reverse 1:
  9999 function calls
  16 milliseconds
Reverse 2:
  5000 function calls
  52 milliseconds

现在为什么函数调用两倍的函数要快 3 倍？我应该如何构建我的递归函数以在 Java 中实现最大速度？

4

3 回答 3

7

这是一个很好的旧算法分析问题。您reverse1应该在 O(n logn) 时间内运行，而需要 O(n²) 时间，因此要反转的字符串越长，速度就reverse2越快。reverse2reverse1

资源使用量不是由调用次数决定的，而是由将字符复制到在每个字符串连接操作中创建的新 String 对象所花费的时间决定的。in 中的字符串连接平均比inreverse2处理更长的字符串，因此它的总执行时间更长。reverse1

  • 在reverse1中，每个字符都被复制 log2(n) 次（其中 n 是原始字符串的长度），因为递归调用树的深度约为 log2(n)。

  • 每个字符被复制的次数等于它在reverse2原始字符串中的位置（±1，我不关心）。这使得每个字符平均有 n/2 个副本。

对于较大的 n，log2(n) 远小于 n/2，因此reverse1往往更快。

于 2012-11-06T16:23:32.370 回答
2

大约 50% 的第一种类型的调用没有做任何工作就结束了，因为str.length() == 1. 这使得具有非平凡工作的调用数量大致相等。如果您在退出条件之后移动derp++并herp++调用，您将获得“非平凡”调用的数量，并且它们将相等。

其他调用也会更快，因为平均而言它们会连接较短的字符串，弥补 3 倍的差异。

于 2012-11-06T16:22:49.730 回答
1

@HenningMakholm's answer is excellent, but I just wanted to throw this out there, based on a comment about iterative methods and immutable strings by @cHao. This would probably be most appropriate for a comment but I wanted the space real estate of an answer...

public static String reverse3(String str){
    StringBuilder sb = new StringBuilder();
    int i;
    for(i = str.length() - 1; i >= 0; i--) {
        sb.append(str.charAt(i));
    }
    return sb.toString();
}

This iterative method which creates only one immutable String object at the end, and runs in O(n) time yields the following results:

  Length: 5406
Reverse 1:
  10811 function calls
  59 milliseconds
  5406 length correctness test
Reverse 2:
  5406 function calls
  126 milliseconds
  5406 length correctness test
Reverse 3:
  3 milliseconds
  5406 length correctness test
于 2012-11-06T17:27:36.673 回答