Ein Werkzeug für die Berechnung der big-O-Zeit-Komplexität von Java-code?
Ich habe eine Frage in Bezug auf die Zeit-Komplexität (big O notation) für Java-software. Gibt es eine Möglichkeit, schnell zu berechnen, oder es zu testen (oder jede website, die rechnen konnte, es wäre mir willkommen). Zum Beispiel möchte ich, um es zu überprüfen für das folgende code-snippet und evtl. verbessern sowie:
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);
- "Time Complexity" bedeutet in der Regel worst-case Zeitkomplexität. Dieses problem hat sich erwiesen, unmöglich.
- Ich meinte (big-O) Komplexität. Bearbeiten Sie die post als gut.
- Wenn Sie wollen, count distinct Ziffern einer Zahl im code ist definitiv nicht die optimale Lösung, sowohl in Zeit und Raum.
- wie würden Sie es verbessern Philipp? Welche Orte sollte korrigiert werden?
- Es gibt keine bestimmten Orte, es ist der ganze Ansatz: Es gibt keine Notwendigkeit für strings, reguläre Ausdrücke und Sätze. Nur einige rechnen (mod, div) und eine einzelne Schleife. Das Ergebnis würde laufen in O(n) Zeit und O(1) Platz, mit n = Anzahl der Ziffern in der Eingabe. Geben Sie mir einige Minuten für den code.
- auch der Vorsatz wäre mehr offensichtliche(!)
Du musst angemeldet sein, um einen Kommentar abzugeben.
Als @emory wies darauf hin, es ist beweisbar unmöglich zu bestimmen, die big-O Zeitkomplexität eines beliebigen Stück code automatisch (der Beweis ist eine Reduktion von der Halteproblem). Es gibt jedoch tools, die versuchen zu Messen, die Komplexität ein Stück code empirisch, indem Sie es auf verschiedene Eingänge. Ein solches Werkzeug ist beschrieben in dem Artikel "Messung von Empirischen Computational Complexity" von Goldsmith, Aiken, und Wilkerson. Es funktioniert, indem Sie versuchen zu tun, eine regression auf das Programm-Laufzeit gegenüber den Eingabe-Größe. Das tool, genannt trend-prof, ist online verfügbar.
Hoffe, das hilft!
Hätte ich die Lösung jemand die Hausaufgaben, aber die Frage war betteln für eine vernünftige Lösung...
Zählen verschiedene Ziffern in einer Zahl erfordert keine strings, sets oder reguläre Ausdrücke, nur einige einfachen Arithmetik.
Die folgende Methode läuft in O(n) Zeit (n = Anzahl der Ziffern in der Eingabe) und die constant-space:
Dieser Arbeit für negative zahlen ist die linke als eine exericse an den Leser 😉
0121212
interpretiert wird als Oktalzahl (führende null) und ist41610
als dezimal-Zahl und somit 4 korrekt ist.