どのような複雑な関数は複雑なループ内の再帰関数

Question

私はこのコードの複雑さを分析しようとしている。 私は、forループが再帰関数の中でao（n）を取るので、そのo（n^2） を述語としました。わからない 。あなたは総複雑性は、ネストされた複雑さの積であり、並び替える機能がNは、文字列の長さであり、そしてループが呼び出されN回呼び出されることに正しい

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も同様であり、ループの呼び出しをもたらす。しかし、ループ内のコードの複雑さ、特にreplaceFirstとinsertを調べる必要があります。ランタイムが文字列の長さに依存するかどうかを判断し、それを掛けてください。私はこれが宿題の問題だと思うので、私はこれをあなたに任せます。