小编aur*_*ron的帖子

我对算法分析非常熟悉,可以告诉Big-O我使用的大多数算法.但是我已经被困了几个小时无法想出我写的这段代码的Big-O.

基本上它是一种为字符串生成排列的方法.它的工作原理是将字符串中的每个字符作为第一个字符,并将其与子字符串的排列组合,减去该字符(递归).

如果我输入代码来计算迭代次数,我就得到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 : …