在递归函数中具有循环的函数的复杂性是什么?

Question

im试图分析此代码的复杂性。我指出它的O(n^2(因为对于循环，请在递归函数中取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，决定它们的运行时是否取决于字符串的长度，并且也与之相比。我怀疑这是一个家庭作业问题，我把这个留给您。