Ideen zur Algorithmenanalyse

Analyse-Framework

1. Verwenden Sie die Algorithmus-Eingabeskala n als Parameter, um die Algorithmuseffizienz zu analysieren

2. Zeitkomplexität: Finden Sie die Grundoperation O(1) und berechnen Sie dann, wie oft sie ausgeführt wird (ignorieren Sie die Multiplikationskonstante und konzentrieren Sie sich nur auf die Anzahl der Erhöhungen)

3. Anzahl der Erhöhungen: log2n

4. Die schlechteste, durchschnittliche und beste Effizienz beziehen sich alle auf die Effizienz, wenn die Eingabegröße n ist (die durchschnittliche Effizienz kann aus bekannten Ergebnissen abgeleitet werden)

Hauptrahmen für die zusammenfassende Analyse:

1. Die Zeiteffizienz und Platzeffizienz des Algorithmus werden als Funktion der Eingabegröße gemessen.

2. Verwenden Sie die Anzahl der Ausführungen der Grundoperationen des Algorithmus, um die Zeiteffizienz zu messen, und verwenden Sie die Anzahl der zusätzlich vom Algorithmus verbrauchten Einheiten, um die Raumeinheit zu messen

3. Wenn die Eingabeskala gleich ist, unterscheidet sich die Effizienz der geschriebenen Algorithmen erheblich. Für diese Art von Algorithmus müssen die schlechteste, durchschnittliche und beste Effizienz analysiert werden

4. Das Hauptanliegen des Frameworks ist: seine Effizienz, wenn die Eingabeskala tendenziell unendlich ist

Asymptotische Notation und grundlegende Effizienztypen

1. O(g(n)) ist die Menge der Funktionen mit Wachstumszeiten

2. Ω(g(n)) ist eine Menge von Funktionen mit Wachstumszeiten >= c*g(n), niedrigerer Ordnung

3. θ(g(n)) ist eine Menge von Funktionen mit Wachstumszeiten = c*g(n) in der gleichen Reihenfolge

Sie können Grenzwerte verwenden, um die Anzahl der Erhöhungen zu vergleichen (Lópidas Gesetz)

Die Gesamteffizienz des Algorithmus wird durch den Teil mit längeren Wachstumszeiten bestimmt.

Allgemeines Schema zur mathematischen Analyse nichtrekursiver Probleme

1. Entscheiden Sie, welcher Parameter die Metrik der Eingabegröße darstellt

2. Informieren Sie sich über die Grundfunktionen des Algorithmus

3. Überprüfen Sie, ob die Anzahl der Grundoperationen nur von der Eingabegröße abhängt. Wenn sie auch von einigen anderen Merkmalen abhängt (z. B. der Position des Elements im Array usw.), analysieren Sie die schlechtesten, durchschnittlichen und beste Effizienz

4. Erstellen Sie einen Summationsausdruck (möglicherweise einen rekursiven Ausdruck) für die Anzahl der Ausführungszeiten der Grundoperation des Algorithmus

5. Verwenden Sie Standardoperationen oder Regeln für Summationsoperationen, um eine geschlossene Formel für die Anzahl der Operationen zu erstellen oder zumindest die Anzahl der Erhöhungen zu bestimmen

Allgemeines Schema zur mathematischen Analyse rekursiver Probleme

1. Entscheiden Sie, welcher Parameter die Metrik der Eingabegröße darstellt

2. Informieren Sie sich über die Grundfunktionen des Algorithmus

3. Überprüfen Sie, ob die Anzahl der Grundoperationen nur von der Eingabegröße abhängt. Wenn sie auch von einigen anderen Merkmalen abhängt (z. B. der Position des Elements im Array usw.), analysieren Sie die schlechtesten, durchschnittlichen und beste Effizienz

4. Stellen Sie für die Anzahl der Ausführungszeiten der Grundoperationen des Algorithmus eine Rekursionsbeziehung und entsprechende Anfangsbedingungen her.

5. Lösen Sie diese Wiederholung oder bestimmen Sie zumindest die Anzahl der Inkremente.

Das obige ist der detaillierte Inhalt vonIdeen zur Algorithmenanalyse. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!