字符串排列的时间复杂度 [英] Time Complexity of Permutations of a String

问题描述

以下示例摘自《破解编程访谈》(第6版).根据本书，以下代码的时间复杂度为O(n ^ 2 * n！). (请参见示例12.第32,33页)

Following example was taken from Cracking the coding interview (version 6) book. As per the book the time complexity of the following code is O(n^2 * n!). (Please refer the example 12. Page 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;

}

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

I am finding it difficult to understand how it was calculated. Following is my thoughts about it.

可以有n！安排.因此至少应该有n个！电话.但是，对于每个呼叫，大约要进行n次工作. (因为它需要遍历传递的字符串).所以答案不应该是O(n * n！)吗?

There can be n! arrangements. So there should be at least n! calls. However, for each call, roughly n times work happens. (as it need to loop through the passed string). So shouldn't the answer be O (n * n!)?

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

But what really happen is for each call the looping need to be done for (n-1) strings. So can we say it should be rather n! * n(n+1)/2

请解释..

推荐答案

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

There are n! possible strings, but each character that's added to the string requires:

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!)

The substring calls and the string concatenation are O(n). For each character in a string that would be O(n^2) and for all strings would be O(n^2 * n!)

这篇关于字符串排列的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！