为什么置换函数的时间复杂度为O(n！) [英] Why Time complexity of permutation function is O(n!)

问题描述

考虑以下代码.

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个字符.
因此，根据这种逻辑，重复关系变为

here the logic, that i think is followed is- it considers each character of the string as a possible prefix and permutes the remaining n-1 characters.
so by this logic recurrence relation comes out to be

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

这显然是O(n！).但是当我使用一个count变量查看Wheather算法确实按n！的顺序增长时，我发现了不同的结果.
对于count ++(在循环内)的2长度字符串运行4次，对于3长度字符串count的值为15，而对于4和5长度字符串则为64和325.
这意味着它比n！更糟.那么为什么要说它(以及产生置换的类似算法)在运行时间上是O(n！).

which is obviously O(n!). but when i used a count variable to see wheather algo really grows in order of n!, i found different results.
for 2-length string for count++(inside for loop) runs 4 times, for 3-length string value of count comes 15 and for 4 and 5-length string its 64 and 325.
It means it grows worse than n!. then why its said that this(and similar algos which generate permuatations) are O(n!) in terms of run time.

推荐答案

人们说此算法为O(n!)，因为存在n!排列，但是(在某种意义上)这里所说的是函数调用-而且函数调用比n!多:

People say this algorithm is O(n!) because there are n! permutations, but what you are counting here are (in a sense) function calls - And there are more function calls than n!:

• str.length() == n时，您进行n通话；
• 对于每个使用str.length() == n - 1的n呼叫，您都执行n - 1呼叫；
• 对于使用str.length() == n - 2的每个n * (n - 1)呼叫，您都进行n - 2呼叫；
• ...

• When str.length() == n, you do n calls;
• For each of these n calls with str.length() == n - 1, you do n - 1 calls;
• For each of these n * (n - 1) calls with str.length() == n - 2 you do n - 2 calls;
• ...

您进行输入长度为k ¹ 的输入str的n!/k!呼叫，由于长度从n到0，因此呼叫总数为:

You do n!/k! calls with an input str of length k¹, and since the length goes from n to 0, the total number of calls is:

sum _{k = 0 ... n} (n！/k！)= n！总和 _{k = 0 ... n} (1/k！)

sum _{k = 0 ... n} (n!/k!) = n! sum _{k = 0 ... n} (1/k!)

但是您可能知道:

sum _{k = 0 ... + oo} 1/k！ = e ¹ = e

sum _{k = 0 ... +oo} 1/k! = e¹ = e

因此，基本上，此总和始终小于常数e(并且大于1)，因此可以说调用次数为O(e.n!)，即O(n!).

So basically, this sum is always less than the constant e (and greater than 1), so you can say that the number of calls is O(e.n!) which is O(n!).

运行时复杂度通常不同于理论上的复杂度.从理论上讲，人们想知道排列的数量，因为该算法可能会检查这些排列中的每一个(因此有效地完成了n!检查)，但实际上还有很多事情要做.

Runtime complexity is often different from theoretical complexity. In theoretical complexity, people want to know the number of permutations because the algorithm is probably going to check each of these permutations (so there are effectively n! check done), but in reality there is much more thing going on.

_{¹ 该公式实际上将为您提供一个值，因为您确实考虑了初始函数调用的结果.}

_{¹ This formula will actually give you one compared to the values you got since you did account for the initial function call.}

这篇关于为什么置换函数的时间复杂度为O(n！)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！