用于计算 Java 代码的大 O 时间复杂性的工具？[已关闭]

algorithm time-complexity java big-o

2022-09-02 13:15:48

闭。此问题不符合堆栈溢出准则。它目前不接受答案。

我们不允许有人向图书、工具、软件库等内容寻求建议。您可以编辑问题，以便可以用事实和引文来回答。

9个月前关闭。

社区在9个月前审查了是否重新打开这个问题，并关闭了它：

原始关闭原因未解决

改进此问题

我有一个关于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);

答案 1

正如@emory所指出的，可以证明不可能自动确定任意代码段的大O时间复杂度（证明是从停止问题中减少的）。但是，有些工具可以尝试通过在几个不同的输入上运行一段代码来经验性地测量代码的复杂性。Goldsmith，Aiken和Wilkerson的论文“测量经验计算复杂性”中描述了一个这样的工具。它的工作原理是尝试对程序的运行时与其输入大小进行回归。该工具名为trend-prof，已停产，但已在此处存档以供参考。

答案 2

我可能正在解决某人的家庭作业，但问题是乞求一个理智的解决方案......

计算数字中的非重复数字不需要字符串，集合或正则表达式，只需要一些简单的算术。

以下方法在 O（n）时间（n = 输入中的位数）和常量空间中运行：

int distinctDigits(int num) {
  if (num == 0) {
    return 1;
  }

  boolean[] digits = new boolean[10];

  while (num > 0) {
    digits[num % 10] = true;
    num /= 10;
  }

  int count = 0;
  for (boolean digit : digits) {
    if (digit) {
      count++;
    }
  }

  return count;
}

为负数做这项工作留给读者;)