Wenn wir ein Problem lösen müssen und viele Möglichkeiten zur Lösung dieses Problems zur Verfügung stehen (z. B. Matrixkettenmultiplikationsproblem), ist zu diesem Zeitpunkt eine Analyse des Algorithmus erforderlich.

Analyse von Algorithmen bedeutet, ihre Komplexität im asymptotischen Sinne abzuschätzen. Der Begriff „Analyse von Algorithmen“ wurde von Donald Knuth geprägt. Die Analyse von Algorithmen ist die Bestimmung der Menge an Zeit- und Raumressourcen, die zur Ausführung erforderlich sind.

Die meisten Algorithmen sind rekursiver Natur, sie verwenden die Divide and Conquer-Strategie. Der rekursive Algorithmus ruft sich selbst für die anderen Eingaben auf. Das ist normalerweise Teil der ursprünglichen Eingabe, hat aber eine kleinere Größe (Unterproblem). Es gibt viele Möglichkeiten, die Wiederholungsbeziehung zu lösen. Sie sind wie folgt:

1. Hauptsatz

2. Wiederholungsbaummethode

3. Substitutionsmethode

4. Änderung der Variablenmethode

Unter all diesen Methoden ist der Mastersatz die schnellste Methode, um die zeitliche Komplexität der Funktion zu ermitteln. Es ist sehr leicht zu verstehen und einfach anzuwenden. Wir müssen uns nur an einige Fälle erinnern. Also los geht’s.