Uno strumento per il calcolo della complessità del tempo grande del codice Java?

Question

Ho una domanda riguardante la complessità del tempo (grande notazione O) per il software Java. C'è un modo per calcolarlo o testarlo rapidamente (o qualsiasi sito web che potrebbe calcolarlo per me sarebbe ben accetto). Per esempio desidero controllare per il seguente frammento di codice ed eventualmente migliorare così:

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

Answer 1

Come @emory indicate, è dimostrabilmente impossibile determinare il tempo complessità O grande di una quantità arbitraria di codice automaticamente (la prova è una riduzione da Halting Problem). Tuttavia, esistono strumenti che possono tentare di misurare empiricamente la complessità di un pezzo di codice eseguendolo su diversi input diversi. Uno di questi strumenti è descritto nel documento "Misurazione della complessità computazionale empirica" ​​di Goldsmith, Aiken e Wilkerson. Funziona tentando di eseguire una regressione sul runtime del programma rispetto alla sua dimensione di input. Lo strumento, chiamato trend-prof, è disponibile online.

Spero che questo aiuti!

Answer 2

potrei essere risolvendo compiti a casa di qualcuno, ma la questione pregavo per una soluzione sana di mente ...

Conteggio cifre distinte in un numero non richiede stringhe, insiemi o espressioni regolari, solo alcuni semplici aritmetica.

Il seguente metodo viene eseguito in O (n) (n = numero di cifre nell'input) e lo spazio costante:

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

Facendo questo lavoro per i numeri negativi viene lasciato come exericse al lettore;)