Programmatisch die Landau-Notation (Big O- oder Theta-Notation) eines Algorithmus finden?

Ich bin es gewohnt, von Hand nach der Landau-Notation (Big O, Theta ...) meiner Algorithmen zu suchen, um sicherzustellen, dass sie so optimiert wie möglich sind, aber wenn die Funktionen wirklich groß und komplex werden, nimmt sie Fahrt auf zu viel Zeit, um es von Hand zu tun. Es ist auch anfällig für menschliche Fehler.

Ich habe einige Zeit mit Codility (Codierungs- / Algo-Übungen) verbracht und festgestellt, dass Sie die Landau-Notation für Ihre eingereichte Lösung erhalten (sowohl in Bezug auf die Zeit als auch in Bezug auf die Speichernutzung).

Ich habe mich gefragt, wie sie das machen ... Wie würden Sie das machen?

Gibt es neben der lexikalischen Analyse oder dem Parsen des Codes noch einen anderen Weg?

Diese Frage betrifft hauptsächlich PHP und / oder JavaScript, aber ich bin offen für jede Sprache und Theorie.

Ich habe mich gefragt, wie sie das machen ... Wie würden Sie das machen?

Ich stelle mir vor, dass sie tatsächlich die Big O-Kennzahlen schätzen ... indem sie das Programm für verschiedene Problemgrößen ausführen, die Zeit- und Raumnutzung messen und Kurven an die Ergebnisse anpassen.

Das Problem bei diesem Ansatz ist, dass es falsch sein kann , wenn die Kostenfunktionen ihre Form ändern, wenn N groß wird; zB 1000 N + N^1.5.

Gibt es neben der lexikalischen Analyse oder dem Parsen des Codes noch einen anderen Weg?

Lexikalische Analyse und Analyse reichen nicht aus. Sie müssen auch einige Überlegungen zum Verhalten des Algorithmus anstellen. Und das automatisch für einen bisher unbekannten Algorithmus zu tun, ist schwierig.

Sie können nicht ohne den Code zu analysieren.

Die folgenden Beispiele mit künstlicher "Inflation / Deflation" der Komplexität zeigen, dass die einfache Messung der Programmlaufzeit nicht ausreicht, um Big-O zuverlässig abzuschätzen

void lets_trick_runtime(int n) {
   if (n == 10 || n == 25 || n == 118) {
      // unfair speed-up
      do_precalculated_solution_in_constant_time(n);
      return;
   }
   if (n == 11 || n == 26 || n == 119) {
      // unfair slow-down
      do_some_fake_processing_in_n_cube_time(n);
      return;
   }
   // fair solution
   do_general_solution_in_quadratic_time(n);
}

Eine Laufzeitschätzung für oben wäre sinnvoll, um falsche Schätzungen zu geben - konstante Zeit für Werte, bei ndenen eine vorberechnete Lösung vorliegt, und kubische Zeit für Werte, bei denen unfair slow-downeintritt - anstelle einer "fairen" quadratischen Zeit.

Ich denke, dass dies nicht möglich ist.

Wenn Sie einige Tests mit einer festen Anzahl unterschiedlicher Eingabegrößen ausführen, können Sie leicht ein Polynom berechnen, das die von Ihnen gemessenen Laufzeiten sehr gut annähert. Sie erhalten also ein Polynom für jedes mögliche Programm, was bedeuten würde P = NP(yeah !;)).

Wenn Sie versuchen, dies mit symbolischer Manipulation zu tun, landen Sie am halting problem. Da Sie nicht entscheiden können, ob Ihr Programm jemals gestoppt wird, können Sie nicht entscheiden, welche Laufzeitkomplexität es haben wird.

Es kann jedoch sehr spezielle Fälle geben, in denen die spätere Methode möglich ist. Aber diese Fälle sind vielleicht so klein, dass es fraglich ist, ob jemals Aufwand bezahlt wird.

Wie würde ich das machen? So wie ich fast jedes Problem löse, möchte ich mich nicht hinsetzen und lösen . Ich simuliere.

Bei vielen Problemen kann es ausreichend sein, den Algorithmus mehrmals mit verschiedenen Größen auszuführen und dann eine Regressionskurve an diese Ergebnisse anzupassen. Das würde schnell einige bestimmte "feste" Gemeinkosten Ihres Algorithmus (den Schnittpunkt der Kurve) identifizieren und wie er skaliert, wenn Ihre Problemgröße zunimmt.

Um besonders komplizierte Lösungen zu erfassen, sind einige Bastelarbeiten erforderlich. Insbesondere wenn Sie jedoch nur nach einer Schätzung des Baseballstadions suchen, sollten Sie diese auf diese Weise erhalten und feststellen können, wie sich Ihre Schätzung von Ihren tatsächlichen Ergebnissen unterscheidet, und entscheiden, ob dies der Fall ist eine akzeptable Annäherung.

Die größte Schwäche meiner Meinung nach bei dieser Methode ist, dass, wenn Ihr Algorithmus wirklich schlecht skaliert , der anfängliche Schritt "ein paar Mal ausführen" hässlich wird. Aber ehrlich gesagt, das ist der Fall, das allein sollte ein Indikator dafür sein, dass Sie zurücktreten und die Dinge überdenken möchten.

Meine Intuition ist, dass eine allgemeine Lösung für dieses Problem unmöglich ist; a priori Fakten über die Laufzeit von Algorithmen zu behaupten, ohne sie auszuführen (Sie spielen auf die lexikalische Analyse an). Das heißt, es ist für einen heuristischen Algorithmus für eine (wahrscheinlich große) Klasse von Algorithmen möglich (da wir dies die ganze Zeit tun), aber ein allgemeiner Algorithmus, um dies zu tun, wäre gleichbedeutend mit der Lösung des Entscheidungsproblems, von dem bekannt ist, dass es nicht so ist möglich (vgl. Church, Turing et al.). Ich bin mir ~ 99,9% sicher, jetzt wo ich darüber nachdenke…