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

11

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.

Julien L.
quelle
4
Überprüfen Sie diese Antwort von SO. Es klingt wie das, wonach Sie suchen.
Deco
2
Wenn Sie ein Programm erstellen können, das dieses Problem für jeden Algorithmus löst, werden Sie als "der Mann, der Turing widerlegt" berühmt.
user281377
1
Beweise dafür, dass es im Allgemeinen unmöglich ist, Laufzeiten zu bestimmen, finden Sie hier und hier - die Antworten dort beweisen sogar noch mehr, als Sie tatsächlich verlangen.
Alex Ten Brink

Antworten:

13

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.

Stephen C.
quelle
6
"Das automatisch für einen bisher unbekannten Algorithmus zu tun ist schwierig" - Genauer gesagt: Es ist gleichbedeutend mit der Lösung des Halteproblems.
Jörg W Mittag
Ähm ... nicht genau. Das Lösen des Halteproblems wäre gleichbedeutend damit, dass dies für alle bisher unbekannten Algorithmen möglich ist.
Stephen C
2
Ja Entschuldigung. Dies für einen Algorithmus zu tun, entspricht dem Nachweis der Beendigung (oder impliziert dies vielmehr).
Jörg W Mittag
1
Die praktischen Aspekte davon sind, dass 1) es unmöglich ist, die Terminierung für einige Algorithmen zu beweisen oder zu widerlegen, aber 2) die meisten Algorithmen dieses theoretische Hindernis nicht haben, aber 3) der Stand der Technik in der Theoremprüfung nicht weit genug fortgeschritten ist in der Lage sein, dies trotzdem zu tun ... außer in relativ einfachen Fällen. Daher meine Aussage, dass ich mir vorstelle, dass sie dies anders machen. Aber natürlich können wir nicht sicher sein, wie sie das wirklich tun, ohne ihren Code zu betrachten.
Stephen C
3

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.

Mücke
quelle
Wenn sie jedoch die "unfairen" Fälle überprüfen, können sie dennoch davon ausgehen, dass der schlimmste Fall tatsächlich die Big-O-Komplexität schätzt.
Yam Marcovic
1

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.

SpaceTrucker
quelle
1
+1, obwohl ich denke, dass das Stoppproblem als Seltenheit angesehen werden könnte.
Yam Marcovic
0

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.

Fomite
quelle
0

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…

sehr dumm
quelle