java - Java プログラムの時間計算量を計算するプログラム

Question

プログラムの時間の複雑さを見つけるためにJavaで簡単なプログラムを作成しようとしています。「for」ループまたは「while」ループを検索し、O(n)またはO(などの反復回数を出力するだけのプログラム2n) など

textarea で i/p プログラムを取得しました。操作を行う方法はありますか?

誰か助けてください。

Answer 1

これは完全な証拠ではありませんが、あなたのために働くでしょう

import java.util.StringTokenizer;



public class Complexity {
    public static void main(String[] args) {

        String input = "for(i=0;i<10;i++)\n{\nfor(i=0;i<10;i++)\n{\nfor(i=0;i<10;i++)\n{\n}\n}\n}\nfor(i=0;i<10;i++)\n{\n}\nfor(i=0;i<10;i++)\n{\nfor(i=0;i<10;i++)\n{\n}\n}";
        int open_bracket=0;
        StringTokenizer t = new StringTokenizer(input);
        String result = "";

        String token="";
        int current = 0;

        System.out.println("CODE \n"+input);

        while(t.hasMoreTokens())
        {

            token = t.nextToken();

            if(token.equals("{")) open_bracket++;

            if(token.equals("}")) open_bracket--;

            if(token.length()>=3) if(token.substring(0, 3).equals("for"))  current++;

            if(open_bracket==0&&token.equals("}"))
            {
                result += " n^"+current+" +";
                current = 0;
            }
        }

        if(result.length()>0) result = result.substring(0, result.length()-1);

        result = "O( "+result+")";

        System.out.println("RESULT = "+result);

    }
}

出力

CODE    

for(i=0;i<10;i++)
{
for(i=0;i<10;i++)
{
for(i=0;i<10;i++)
{
}
}
}
for(i=0;i<10;i++)
{
}
for(i=0;i<10;i++)
{
for(i=0;i<10;i++)
{
}
}

RESULT = O(  n^3 + n^1 + n^2 )