字符串排列的时间复杂度

以下示例取自《破解编码面试》（第 6 版）一书。根据本书，以下代码的时间复杂度为 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

请解释一下..

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

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

The substring调用和字符串连接是O(n)。对于字符串中的每个字符O(n^2)对于所有字符串来说都是O(n^2 * n!).

EDIT:

我计算了通过串联创建字符串的复杂性O(n^2)但乘以字符串数量是不准确的，因为字符串共享公共前缀，因此存在大量重复计算。

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