Gibt es irgendwelche Tools, die Code-Analyse durchführen für Big-O Komplexität bestimmen können?

Question

Ich habe nichts da draußen gesehen, und ich vermute, die Schwierigkeiten mit der Definition von „n“ da in der Regel für eine komplexe Funktion für die Analyse es sei mehr als nur ein oder zwei Variablen zu definieren.

Es gibt Analysetools für zyklomatische Komplexität aber gibt es diejenigen, für die Zeit (und / oder Raum) Komplexität? Wenn ja welche, wenn nicht, warum nicht? Ist es nicht machbar? Unmöglich? Jemand hat einfach nicht dazu gekommen?

Im Idealfall würde es für die Anwendung so etwas wie Gesamtkomplexität sein (Definition von verschiedener möglicher „n“ s) sowie für jede Methode in der App

Edit: So ist es wie eine exakte Lösung scheint wegen des Halting Problems jedoch nicht möglich ist, ist eine Art von heuristischer Annäherung möglich? Ich weiß, dass für praktische Zwecke ein guter Profiler viel nützlicher Informationen geben wird, aber es scheint wie ein interessantes Problem.

Auch, wie etwa eine, die für eine bestimmte Untergruppe von Programmen berechnet?

Answer 1

Leider gibt es dieses Problem der Halting Problem genannt ...

Answer 2

Nein, das ist nicht möglich, aufgrund des Halteproblems.

Wenn Sie dies tun möchten, dass Ihre Anwendungen zu verbessern, können Sie Profilierung statt betrachten. Es würde dir erlauben, zu-Punkt-Pin, was tatsächlich die meiste Zeit. So kann man (n ^ 3) Algorithmus, der nur auf kleine Datensätze läuft keine Zeit Optimierung eines O verbringen.

Answer 3

Ein paar thoughs:

Echt Computer sind etwa deterministischen endlichen Automaten, so dass das Halteproblem ist nicht wirklich eine praktische Einschränkung. Eine praktische Einschränkung ist ein Algorithmus, der mehr Zeit zu laufen, als man sich wie Warte nimmt, keine Brute-Force-Methoden der Analyse auszuschließen.

Um eine ungefähre Vorstellung von der Komplexität eines Algorithmus zu erhalten, können Sie es jederzeit auf einer Reihe von zufälligen Eingaben laufen und die Zeit genommen, messen. Dann zeichnen Sie eine Kurve durch die Daten.

Die Analyse der Komplexität von Algorithmen kann ziemlich kompliziert sein, einige kreative Schritte erfordern. (Siehe zum Beispiel Analyse von quicksort). Das Problem ist eng mit der logischen Theorembeweisen und Programmverifikation zusammen. Es könnte sein, möglich, ein nützliches Werkzeug zu konstruieren, die halbautomatische Lösung von Komplexität ermöglicht, das heißt ein Werkzeug, das systematisch für Lösungen gegeben Hinweise von einem Menschen sucht, aber es ist sicherlich nicht einfach.

Answer 4

Sie niemals ein Werkzeug, dies zu tun gesehen, aber wir Werkzeuge utilize Profilierungs eine bessere Vorstellung davon zu bekommen, wo die Engpässe sind. Es ist nicht immer klar, und ich habe ein paar Mal von Dingen überrascht, dass ich dachte, eine wirklich lange Zeit in Anspruch nahm sehr wenig zu nehmen und umgekehrt. In der .NET-Welt habe ich verwendet ANTS und die < a href = "http://www.jetbrains.com/profiler/" rel = "nofollow noreferrer"> JetBrains Tools.