Time Complexity verstehen

Das Ziel von Nicolas Descartes Artikel ist es, die Überlegenheit eines Algorithmus gegenüber einem anderen zu bestimmen, wenn zwei oder mehr Optionen zur Auswahl stehen. Dabei bemüht er sich um einfache Erklärungen, scheut aber auch die komplizierten Details nicht. Dabei stützt er sich auf diese Lehrbücher:

Darum geht es: Hinter jeder Aufgabe, die einem Computer zugewiesen wird, steht jedoch eine Folge von Anweisungen, die in einer bestimmten Reihenfolge ausgeführt werden müssen. Innerhalb dieses Rahmens können Variationen in der Art und Weise auftreten, wie Anweisungen definiert werden, was die Erforschung von Methoden erforderlich macht, die effizienter sind als andere. Dann stellt sich die Frage: Wie kann man feststellen, dass eine Methode einer anderen überlegen ist? In Wirklichkeit gibt es auf diese Frage keine eindeutige Antwort, da der Begriff "überlegen" für jeden Einzelnen eine andere Bedeutung haben kann. Einige mögen argumentieren, dass eine Methode überlegen ist, wenn sie weniger Speicherplatz benötigt, was besonders für Geräte wichtig ist, bei denen die Speicherverwaltung kritisch ist, wie zum Beispiel bei Mikrocontrollern. Andere halten eine Methode für überlegen, wenn sie leicht zu verstehen und zu erklären ist. Descartes Beitrag definiert eine Methode als überlegen, wenn sie weniger Zeit zur Ausführung benötigt als andere.

Sein Ziel ist es also, unter mehreren Algorithmen diejenigen herauszufinden, die besser geeignet sind, früher beendet zu werden. Diese Analyse der Zeit, die ein Algorithmus für die Ausführung einer Aufgabe benötigt, wird als Zeitkomplexität bezeichnet und ist seit den Anfängen der Informatik von entscheidender Bedeutung.

Die weiteren Ausführungen und seine einfachen Beispiele finden Sie in diesem CodeProject-Beitrag von Nicolas Descartes.