Ich habe eine Frage bezüglich der zeitlichen Komplexität (große O-Notation) für Java-Software. Gibt es eine Möglichkeit, es schnell zu berechnen oder zu testen (oder eine Website, die es für mich berechnen könnte, wäre willkommen). Zum Beispiel möchte ich es für das folgende Codefragment überprüfen und möglicherweise auch verbessern:
%Vor%Wie @emory gezeigt hat, ist es nachweislich unmöglich, die Komplexität der großen O-Zeit eines beliebigen Codes automatisch zu bestimmen (der Beweis ist eine Reduktion von Halteproblem ). Es gibt jedoch Tools, die versuchen können, die Komplexität eines Codeteils empirisch zu messen, indem sie auf mehreren verschiedenen Eingängen ausgeführt werden. Ein solches Werkzeug wird in dem Aufsatz "Measuring Empirical Computational Complexity" von Goldsmith, Aiken und Wilkerson beschrieben. Es funktioniert, indem versucht wird, eine Regression der Laufzeit des Programms gegenüber der Eingabegröße durchzuführen. Das Tool, trend-prof , ist online verfügbar.
Hoffe, das hilft!
Ich könnte vielleicht jemandes Hausaufgaben lösen, aber die Frage war, eine vernünftige Lösung zu suchen ...
Das Zählen verschiedener Ziffern in einer Zahl erfordert keine Strings, Mengen oder regulären Ausdrücke, nur einige einfache Arithmetik.
Die folgende Methode wird in O (n) -Zeit (n = Anzahl der Ziffern in der Eingabe) und konstantem Leerzeichen ausgeführt:
%Vor%Diese Arbeit für negative Zahlen zu machen, bleibt dem Leser überlassen;)
Tags und Links algorithm java time-complexity big-o