小编典典

用于计算Java代码的big-O时间复杂度的工具吗?

algorithm

我有一个关于Java软件的时间复杂度(大O表示法)的问题。有没有一种快速计算或测试它的方法(或者欢迎任何可以为我计算它的网站)。例如,我想检查一下以下代码片段,并且可能还会进行改进:

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);

阅读 381

收藏
2020-07-28

共1个答案

小编典典

正如@emory指出的那样,证明自动确定任意一段代码的big-O时间复杂度是不可能的(证明是Halting
Problem
的减少)。但是,有些工具可以尝试通过在几个不同的输入上运行来凭经验来测量代码的复杂性。Goldsmith,Aiken和Wilkerson的论文“测量经验计算复杂性”中描述了一种这样的工具。它通过尝试对程序的运行时间与其输入大小进行回归来工作。该工具称为
Trend-prof (已停产),可供参考。

希望这可以帮助!

2020-07-28