用于计算Java代码的大O时间复杂度的工具？

我有一个关于Java软件的时间复杂度（大O表示法）的问题。有没有办法快速计算或测试它（或任何可以为我计算的网站都会受到欢迎）。例如，我想检查它的下面的代码片断，并可能提高，以及：用于计算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);

来源

2012-03-31 aretai

“时间复杂度”通常意味着最坏情况下的时间复杂度。这个问题已被证明是不可能的。 – emory 2012-03-31 18:34:59

我的意思是（大O）复杂性。也将编辑帖子。 – aretai 2012-03-31 18:38:54

如果你想计算一个数字中不同的数字，那么这段代码绝对不是时间和空间上的最佳解决方案。 – 2012-03-31 18:46:59

正如@emory指出的那样，它可证明是不可能确定的任意片的大O时间复杂度自动编码（证明是从Halting Problem减少）。然而，有些工具可以尝试通过在几个不同的输入上运行来测试一段代码的复杂性。 Goldsmith，Aiken和Wilkerson在论文“衡量经验计算复杂性”中描述了一种这样的工具。它通过尝试对程序的运行时间与其输入大小进行回归来实现。该工具名为trend-prof，可在线获取。

希望这会有所帮助！

来源

2012-03-31 18:42:42 templatetypedef

您说有些工具可以通过运行不同的输入来测量复杂性。与用户自己使用不同的输入来运行他的代码并计算时间有什么不同？两者是否会给出相同的结果？自动与手动？ – Faizan 2013-03-03 21:04:47

@ Faizan-该工具不仅仅是运行程序。它增加了大量的二进制工具来测量单个函数/代码块，而且这比手工完成要容易得多。原则上，您可以手动执行相同的操作，但这会变得非常困难。 – templatetypedef 2013-03-03 22:31:28

@templatetypedef如果您提供论文的名称，而不仅仅是“在本文中”，因为链接经常被打破，它总是有益的。 – Vishrant 2018-01-17 01:51:20

我可能会解决别人的功课，但问题是乞求一个健全的解决方案...

计数在多个不同的数字，不需要串，套或正则表达式，只是一些简单的算术。

下面的方法在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; 
}

使这项工作对于负数留给读者作为exericse到读取器; ）

来源

2012-03-31 19:05:49

不，这不是我的作业，谢谢。其实我也想过这种方法;然而，认为转换为字符串，然后使用Set会更有效率（时间复杂度）。 – aretai 2012-03-31 19:12:40

我希望你仍然觉得这个代码有用:) – 2012-03-31 19:13:46

是的，这是一个整洁的解决方案，以及谢谢。虽然它并不直接回答我的问题（如上面的问题），但是你有1。 – aretai 2012-03-31 19:15:10

用于计算Java代码的大O时间复杂度的工具？

回答

相关问题