字符串排列的时间复杂度

本文介绍了字符串排列的时间复杂度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

以下示例摘自《破解编程访谈》(第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!)