Narzędzie do obliczania skomplikowanej złożoności kodu Java w czasie O?

Question

Mam pytanie dotyczące złożoności czasowej (duża notacja O) dla oprogramowania Java. Czy istnieje sposób, aby szybko obliczyć lub przetestować go (lub jakakolwiek strona internetowa, która mogłaby go obliczyć, byłaby mile widziany). Na przykład chciałbym sprawdzić to na poniższym fragmencie kodu i ewentualnie poprawić także:

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

Jak @emory wskazał, że jest provably niemożliwe do określenia czasu złożoności big-O z dowolnego kawałka kod automatycznie (dowodem jest zmniejszenie z Halting Problem). Istnieją jednak narzędzia, które mogą próbować empirycznie zmierzyć złożoność kawałka kodu, uruchamiając go na kilku różnych wejściach. Jedno takie narzędzie opisano w artykule "Pomiar empirycznej złożoności obliczeniowej" Goldsmitha, Aikena i Wilkersona. Działa poprzez próbę regresji w środowisku wykonawczym programu w porównaniu z jego wielkością wejściową. Narzędzie o nazwie trend-prof jest dostępne online.

Mam nadzieję, że to pomoże!

Answer 2

mogę być rozwiązywanie czyjąś pracę domową, ale pytanie było prosząc o sane rozwiązanie ...

Liczenie wyraźne cyfry numeru nie wymaga strun, zestawy lub wyrażeń regularnych, zaledwie kilka prostych arytmetyki.

Poniższa metoda przebiega O (n) (n = liczba cyfr w wejście) oraz stałej powierzchni:

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

uruchomienie tego liczb ujemnych pozostanie jako exericse do czytnika;)