Java选择递归函数

Question

我在这里有两个不同的递归函数来反转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中的最大速度？

Answer 1

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

资源使用不是由调用次数决定,而是由将字符复制到每个字符串连接操作中创建的新String对象所花费的时间.字符串连接平均比较reverse2长的字符串工作,因此它的总执行时间更长.reverse1

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

• 在reverse2每个字符中复制的次数等于它在原始字符串中的位置(±1,我不在乎).这使得每个角色平均有n/2个副本.

对于大n,log2(n)远小于n/2,因此reverse1趋于更快.