字符串排列的时间复杂度

Question

以下示例取自 Cracking the coding interview (version 6) book。根据本书，以下代码的时间复杂度为 O(n^2 * n!)。(请参考例子12.第32,33页)

public static void main(String[] args) {
    new PermutationsTest().permutations("ABCD");
}

void permutations(String string) {
    permutations(string, "");
}

static int methodCallCount = 0;

void permutations(String string, String perfix) {


    if (string.length() == 0) {
        System.out.println(perfix);
    } else {
        for (int i = 0; i < string.length(); i++) {
            String rem = string.substring(0, i) + string.substring(i + 1);
            permutations(rem, perfix + string.charAt(i));
        }
    }

    System.out.format("Method call count %s \n", methodCallCount);
    methodCallCount += 1;

}

我发现很难理解它是如何计算的。以下是我对此的看法。

可以有n！安排。所以应该至少有n！调用。但是，对于每次调用，大约会发生 n 次工作。（因为它需要遍历传递的字符串）。那么答案不应该是 O (n * n!) 吗？

但真正发生的情况是，每次调用都需要对 (n-1) 个字符串进行循环。所以我们可以说它应该是n！* n(n+1)/2

请解释..

Answer 1

有n!可能的字符串，但添加到字符串中的每个字符都需要：

String rem = string.substring(0, i) + string.substring(i + 1);
permutations(rem, perfix + string.charAt(i));

该substring呼叫和字符串连接的O(n)。对于字符串中的每个字符，O(n^2)对于所有字符串都将是O(n^2 * n!).

编辑：

我计算了通过连接创建字符串的复杂性，O(n^2)但是乘以字符串的数量是不准确的，因为字符串共享公共前缀，因此那里有很多重复计算。

由于对最终字符串的调用次数远多于其余字符串，因此它们在复杂性中占主导地位，因此它们是唯一需要计算的。所以我认为我们可以将复杂性降低到O(n * n!).