相关疑难解决方法(0)

考虑以下代码.

public class Permutations {
    static int count=0;
    static void permutations(String str, String prefix){
        if(str.length()==0){
            System.out.println(prefix);
        }
        else{
            for(int i=0;i<str.length();i++){
                count++;
                String rem = str.substring(0,i) + str.substring(i+1);
                permutations(rem, prefix+str.charAt(i));
            }
        }

    }
    public static void main(String[] args) {
        permutations("abc", "");
        System.out.println(count);
    }

}

这里我认为遵循的逻辑是 - 它将字符串的每个字符视为可能的前缀,并置换剩余的n-1个字符.
所以通过这种逻辑,复发关系就出现了

T(n) = n( c1 + T(n-1) )          // ignoring the print time

这显然是O(n!).但是当我使用一个计数变量看到天体确实按照n!的顺序增长时,我发现了不同的结果.
对于计数++的2长度字符串(在for循环中)运行4次,对于3长度字符串计数值为15,对于4和5长度字符串其64和325.
这意味着它比n!更糟糕.那么为什么它说这个(以及产生permuatations的类似算法)就运行时而言是O(n!).