Java 两种递归方法的复杂度

Question

public static String rec1 (String s) {

    int n = s.length()/2; 
    return n==0 ? s : rec1(s.substring(n)) + rec1(s.substring(0,n)); 
}


public static String rec2 (String s) {
    return s.length()<=1 ? s : rec2(s.substring(1)) + s.charAt(0); 
}

为什么 rec2 的复杂度大于 rec1？

我对每个迭代都进行了 10.000 次迭代，并使用 System.nanoTime() 测量了执行时间，结果如下：

rec1: Stringlength: 200  Avgtime: 19912ns Recursive calls: 399

rec1: Stringlength: 400  Avgtime: 42294 ns Recursive calls: 799

rec1: Stringlength: 800  Avgtime: 77674 ns Recursive calls: 1599

rec1: Stringlength: 1600 Avgtime: 146305 ns Recursive calls: 3199

rec2: Stringlength: 200  Avgtime: 26386 ns Recursive calls: 200

rec2: Stringlength: 400  Avgtime: 100677 ns Recursive calls: 400

rec2: Stringlength: 800  Avgtime: 394448 ns Recursive calls: 800

rec2: Stringlength: 1600 Avgtime: 1505853 ns Recursive calls: 1600

所以当字符串长度为 1600 时，rec1 比 rec2 快 10 倍。我正在寻找一个简短的解释。

Answer 1

根据 Time complexity of Java's substring()，String#substring 现在复制支持数组，因此具有 O(n) 时间复杂度。

利用这个事实可以看出 rec1 具有时间复杂度 O(n log n) 而 rec2 具有时间复杂度 O(n^2).

从首字母 String s = "12345678" 开始。为简单起见，我将长度取为 2 的幂。

rec1:

s 拆分为 "1234" 和 "5678".
这些分为"12"、"34"、"56"、"78"
这些分为 "1"、"2"、"3"、"4"、"5"、"6"、"7" , "8"

这里有 3 个步骤，因为 log(8) = 3。每一步都复制char，所以复制的字符总数是O(n log n)。当 String 以相反的顺序重新组装时，上面的 Strings 现在使用以下步骤连接在一起：

字符串被连接成"21"、"43"、"65"、"87"
字符串被连接成"4321"、"8765"
将字符串连接起来形成 "87654321"。

这又是一共O(n log n)个复制的字符！

rec2:

s 拆分为 "1" 和 "2345678".
"2345678" 拆分为 "2" 和 "345678".
"345678" 拆分为 "3" 和 "45678".
"45678" 拆分为 "4" 和 "5678"。
"5678" 拆分为 "5" 和 "678".
"678" 拆分为 "6" 和 "78".
"78" 拆分为 "7" 和 "8"。

总共 8 + 7 + 6 + 5 + 4 + 3 + 2 = 35 个复制的字符。如果你懂代数，一般来说这将是 (n * (n+1)) / 2 - 1 个复制的字符，所以 O(n^2).

全部倒序拼装后，字数又是O(n^2)

Answer 2

让我们调查一下性能差异：

String.substring()

substring 在 java 中非常便宜（直到 Java 7 Update 6）因为它不复制原始数据而只更新同一数组上的偏移量。

字符串覆盖 + 运算符

这里出现了差异，因为被覆盖的 + 运算符在非文字字符串的情况下使用 StringBuilder。如果您向下钻取 StringBuilder.append() 方法的实现，您最终会找到对 System.arraycopy().

所以不同之处在于 System.arraycopy() 在 rec1 中处理呈指数递减的数组大小，而在 rec2 中只处理线性递减的数组大小。

Answer 3

（这是关于时间复杂度的更正版本）

虽然递归的次数实际上是线性的（因为递归在每个级别被调用两次）但是就复制字符而言，这两种方法之间存在差异很关心。

每个方法都在内部进行两次复制操作——一个用于 substring（在 Java 7 中），一个用于 concat（由 [=12 表示） =] 运算符).

在rec2中，它一直复制字符串的右侧，直到只剩下一个字符。所以字符串的最后一个字符被复制depth次，深度是线性的。所以线性步骤乘以线性副本（它实际上是一个系列）给出 O(n²).

在rec1中，每个字符要么被复制到左子串，要么被复制到右子串。但是没有字符被复制超过 depth 次 - 直到我们到达单字符子字符串。所以每个字符被复制 log n 次。虽然递归调用了两次，但并不是对同一个字符调用，所以两次调用导致的日志取消不影响每个字符的拷贝数。

重建也是如此。相同的副本以相反的方式发生。

副本数 - n 个字符乘以 log n 的 depth，得到 O(n log n)。执行的步骤数 - O(n)，因此步骤数不如副本数重要，总复杂度为 O(n log n)。

此外，还有 space 复杂性。 rec1 在其递归中达到 O(log n) 的深度，也就是说，它占用 O(log n) 的堆栈 space。它这样做了两次，但这并没有改变 big-O。相反，rec2 达到 O(n) 的深度。

在我的机器上，运行两个长度为 16384 的字符串的方法导致 rec2 的堆栈溢出。 rec1 顺利完成。当然，这根据您的 JVM 设置而有所不同，但您明白了。

Java 两种递归方法的复杂度

Java complexity of two recursive methods

java

methods

recursion

complexity-theory