用於計算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時間複雜度的工具？

回答

相關問題