查找java程序时间复杂度的程序 [英] Program to fnd Time Complexity of a java program

问题描述

我一直在尝试用 Java 编写一个简单的程序来查找程序的时间复杂度.该程序只搜索for"循环或while"循环并打印迭代次数，例如 O(n)或 O(2n) 等

I've been trying to write a simple program in java to find time complexity of a program.A program whih just searches for "for" loop or "while" loop and prints the no of iteration such as O(n) or O(2n) etc.

我在 textarea 中得到了 i/p 程序.有什么方法可以进行操作吗?

I got the i/p program in textarea.Is there any way by which i could do the opertaion?

请任何人帮助我.

推荐答案

这不是完整的证据，但对你有用

This is not full proof, but would work for you

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 )

这篇关于查找java程序时间复杂度的程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！