Rekurrenzen und Master-Theorem
Das nächste Thema im Bereich der Algorithmusentwicklung oder -beschreibung behandelt Rekurrenzen. Diese stellen ein mathematisches Konzept dar, um Laufzeiten rekursiver Algorithmen zu beschreiben. Insbesondere werden mit Hilfe von Rekurrenzen Algorithmen beschrieben, die dem Prinzip „Teile und herrsche“ folgen. In diesem Artikel werde ich detailliert erläutern, was dies bedeutet und wie man die Laufzeit solcher Algorithmen bestimmen kann. Für diesen Algorithmus ist es sinnvoll, wenn bereits Wissen zur O-Notation vorhanden ist. Andererseits habe ich hier einen Artikel zur O-Notation und Laufzeitanalyse von Algorithmen. Rekurrenzgleichungen Eine Rekurrenzgleichung hat folgende Struktur. Sie beinhaltet die 4 Konstanten a,b,c,d die alle positiv sein müssen. N…
