Wie berechnet man die exakte Komplexität eines Algorithmus?

Question

Ohne auf asymptotische Notation zurückgreifen zu müssen, ist mühsame Schrittzählung der einzige Weg, um die zeitliche Komplexität eines Algorithmus zu erhalten? Und ohne Schrittzählung jeder Codezeile können wir zu einer großen O-Darstellung eines Programms gelangen?

Details: Versuch, die Komplexität mehrerer numerischer Analysealgorithmen herauszufinden, welche für die Lösung eines bestimmten Problems am besten geeignet sind. Zum Beispiel - Von der Regula-Falsi oder Newton-Rhapson-Methode zur Lösung von Gleichungen ist die Absicht, die genaue Komplexität jeder Methode zu bewerten und dann zu entscheiden, welche Methode weniger komplex ist (Wert von 'n' oder was auch immer Argumente geben).

Answer 1

Der einzige Weg --- nicht der "einfache" oder harte Weg, aber der einzige vernünftige Weg --- die genaue Komplexität eines komplizierten Algorithmus zu finden, ist es zu profilieren. Eine moderne Implementierung eines Algorithmus hat eine komplexe Interaktion mit numerischen Bibliotheken und mit der CPU und ihrer Gleitkommaeinheit. Zum Beispiel ist der Zugriff im Cache-Speicher viel schneller als der Zugriff außerhalb des Cache-Speichers, und darüber hinaus kann es mehr als eine Cache-Ebene geben. Das Zählen von Schritten ist wirklich viel besser für die asymptotische Komplexität geeignet, die Ihrer Meinung nach für Ihre Zwecke nicht ausreicht.

Aber, wenn Sie Schritte automatisch zählen möchten, gibt es auch Möglichkeiten, dies zu tun. Sie können jeder Codezeile einen Zählerinkrementbefehl (wie "bloof ++;" in C) hinzufügen und dann den Wert am Ende anzeigen.

Sie sollten auch über die ausgefeiltere Zeitkomplexitätsausdruck f (n) * (1 + o (1)) wissen, die auch für analytische Berechnungen nützlich ist. Zum Beispiel vereinfacht sich n^2 + 2 * n + 7 zu n^2 * (1 + o (1)). Wenn der konstante Faktor Sie über die übliche asymptotische Notation O (f (n)) stört, ist diese Verfeinerung eine Möglichkeit, den Überblick zu behalten und dennoch vernachlässigbare Terme zu verwerfen.

Answer 2

Der 'einfache Weg' ist es zu simulieren. Versuchen Sie Ihre Algorithmen mit vielen Werten von n und vielen verschiedenen Daten, zeichnen Sie die Ergebnisse und passen Sie dann die Kurve im Diagramm an eine Gleichung an.

Ihre Ergebnisse sind möglicherweise nicht genau richtig und sie sind nur so gut wie Ihre Fähigkeit, gute Testdaten zu generieren, aber in den meisten Fällen wird dies funktionieren.

Answer 3

z. - Von der Regula-Falsi oder Newton-Rhapson-Methode zur Lösung von Gleichungen ist die Absicht, die genaue Komplexität jeder Methode zu bewerten und dann zu entscheiden, welche Methode weniger komplex ist (Wert von 'n' oder was auch immer Argumente geben).

Ich glaube nicht, dass es möglich ist, diese Frage allgemein für nichtlineare Löser zu beantworten. Sie könnten eine genaue Anzahl von Berechnungen pro Iteration durchführen, aber Sie werden nie im Allgemeinen wissen, wie viele Iterationen es dauern wird, bis jeder Solver konvergiert. Es gibt andere Komplikationen, wie die Jacobi für Newton's, die die Komplexität der Computer noch schwieriger machen könnte.

Zusammenfassend ist der effizienteste nichtlineare Löser immer abhängig von dem Problem, das Sie lösen. Wenn die Vielfalt der Probleme, die Sie lösen, sehr begrenzt ist, werden Sie wahrscheinlich eine Reihe von Experimenten mit verschiedenen Solvern durchführen und die Anzahl der Iterationen und die CPU-Zeit messen.