这个算法的复杂度是多少?

I'm fairly familiar with algorithm analysis and can tell the Big-O of most algorithms I work with. But I've been stuck for hours unable to come up with the Big-O for this code I write.

我对算法分析相当熟悉，可以告诉我所使用的大多数算法的大o。但是我已经被困了好几个小时，无法为我写的这段代码写出大o。

Basically it's a method to generate permutations for a string. It works by making each character in the string the first character and combine it with the permutations of the substring less that character (recursively).

基本上它是为字符串生成排列的方法。它的工作原理是将字符串中的每个字符作为第一个字符，并将其与子字符串的排列组合(递归地)组合起来。

If I put in the code to count the number of iterations, I've got something between O(N!) and O(N^N). But I couldn't figure out how to analyse it mentally. Any suggestion is much appreciated!

如果我把代码中计算的迭代次数,我有事在O(N)和O(N ^ N)。但我不知道如何在心理上分析它。非常感谢您的建议!

import java.util.ArrayList;
import java.util.List;

public class Permutation {

   int count = 0;

   List<String> findPermutations(String str) {
      List<String> permutations = new ArrayList<String>();
      if (str.length() <= 1) { 
         count++;
         permutations.add(str);
         return permutations;
      }
      for (int i = 0; i < str.length(); i++) {
         String sub = str.substring(0, i) + str.substring(i + 1);
         for (String permOfSub : findPermutations(sub)) {
            count++;
            permutations.add(str.charAt(i) + permOfSub);
         }
      }
      return permutations;
   }

   public static void main(String[] args) {
      for (String s : new String[] {"a", "ab", "abc", "abcd", "abcde", "abcdef", "abcdefg", "abcdefgh"}) {
         Permutation p = new Permutation();
         p.findPermutations(s);
         System.out.printf("Count %d vs N! %d%n", p.count, fact(s.length()));
      }
   }

   private static int fact(int i) {
      return i <= 1 ? i : i * fact(i-1);
   }
}

Edit 1: add test program

编辑1:添加测试程序。

Edit 2: add count++ in base case

编辑2:在基本情况下添加count++。

1 个解决方案

#1

The recurrence equation: T(n) = n*(T(n-1) + (n-1)!), T(1) = 1 where n = str.length.

递归式:T(n) = n*(T(n-1) + (n-1)!)， T(1) = 1，其中n =

WolframAlfa says that the solution is n*(1)_n i.e., n*n!.

WolframAlfa说这个解是n*(1)n。n * n !。

The above assumes that all string operations are O(1). Otherwise if the cost of String sub = ... and permutations.add(str.charAt(i) + permOfSub) lines is considered O(n) then the equation is:

上面假设所有字符串操作都是O(1)。否则，如果String sub =…加(str.charAt(i) + permOfSub)线被认为是O(n)，然后方程为:

T(n+1)=(n+1)*(n + T(n) + n!*(n+1))

T(n) ~ (n*n+2*n-1)*n! i.e., O(n!*n*n)

T(n)~(n * n + 2 * n - 1)* n !即。* n * n,O(n !)

#1