java - 递归函数内部有循环的函数的复杂性是多少

Question

我正在尝试分析这段代码的复杂性。我预测它的 o(n^2)因为 for 循环在递归函数中采用 o(n)，即采用 o(n)o(n) * o(n) = o(n^2)但是我不确定。

public class main 
{

    static Set<String> setString = new HashSet<>();

    public static void main(String[] args) 
    {
        // TODO Auto-generated method stub
        main m = new main();
        m.permute("sanad", 0);
        for(String s : setString)
        {
            System.out.println(s);
        }

    }


    public void permute(String str , int i )
    {
        if (i>=str.length())
        {
            return;
        }


        for(int j = 0 ; j < str.length();j++)
        {
            StringBuilder b = new StringBuilder(str. replaceFirst(String.valueOf(str.charAt(i)), ""));
            b.insert(j,str.charAt(i));
            setString.add(b.toString());
        }

        permute(str, ++i);
    }

}

Answer 1

您是正确的，因为总复杂度是嵌套复杂度的乘积，并且置换函数被调用了 n 次，其中 n 是字符串的长度，循环也被调用 n 次，导致 n^2 次循环调用。但是，您还必须查看循环内代码的复杂性，尤其是 replaceFirst 和 insert，确定它们的运行时间是否取决于字符串的长度，然后乘以与此同时。我怀疑这是一道家庭作业题，所以我把它留给了你。