一种工具，计算的Java code中的大O的时间复杂度？ [英] A tool for calculating the big-O time complexity of Java code?

问题描述

我有一个关于时间复杂度（大O符号）为Java软件的问题。有没有一种方法可以快速计算或测试（或任何网站，可以计算出这对我来说将受到欢迎）。比如我想请检查是否有code下面的代码片段，并有可能提高，以及：

  INT DCOUNT = 24423567;
        INT一个= 0;
        如果（DCOUNT == 0）{
            一个= 1;
        }

        柱DS = Integer.toString（DCOUNT）;
        串[] SA = ds.split（？（小于=）。）;
        HashSet的HS =新的HashSet（）;
        Collections.addAll（HS，SA）;
        一个= hs.size（）;
        如果（DCOUNT℃，）
            一个 - ;

        的System.out.println（一）;
 

解决方案

由于@emory指出，这可证明是不可能确定一个任意一张code自动（证明是一个的大O的时间复杂度减少从停机问题）。然而，也有可以尝试凭经验通过在几个不同的输入运行它以测量一块code的复杂工具。一个这样的工具在本文中所描述的 ，然后作品通过尝试做一个回归的程序的运行时间与它的投入规模。该工具名为 趋势教授 ，可在网上。

希望这有助于！

I have a question regarding time complexity (big O notation) for Java software. Is there a way to quickly calculate or test it (or any website that could calculate it for me would be welcomed). For example I would like to check it for the following snippet of code and possibly improve as well:

int dcount = 24423567;
        int a = 0;
        if (dcount == 0){
            a = 1;
        }

        String ds = Integer.toString(dcount);
        String[] sa = ds.split("(?<=.)");
        HashSet hs = new HashSet();
        Collections.addAll(hs, sa);
        a = hs.size();
        if (dcount < 0)
            a--;

        System.out.println(a);

解决方案

As @emory pointed out, it is provably impossible to determine the big-O time complexity of an arbitrary piece of code automatically (the proof is a reduction from the Halting Problem). However, there are tools that can attempt to measure the complexity of a piece of code empirically by running it on several different inputs. One such tool is described in this paper, and works by attempting to do a regression on the program's runtime versus its input size. The tool, called trend-prof, is available online.

Hope this helps!

这篇关于一种工具，计算的Java code中的大O的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！