Algorithmen in einer Kurzfassung, 2.

Kapitel 2. Die Mathematik der Algorithmen

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

Einer der wichtigsten Faktoren bei der Auswahl eines Algorithmus ist die Geschwindigkeit, mit der er voraussichtlich abgeschlossen werden kann. Die voraussichtliche Rechenzeit eines Algorithmus zu bestimmen, ist ein mathematischer Prozess. In diesem Kapitel werden die mathematischen Werkzeuge vorgestellt, die hinter dieser Zeitvorhersage stehen. Nach der Lektüre dieses Kapitels solltest du die verschiedenen mathematischen Begriffe verstehen, die in diesem Buch - und in der übrigen Literatur, die Algorithmen beschreibt - verwendet werden.

Größe einer Probleminstanz

Eine Instanz eines Problems ist ein bestimmter Eingabedatensatz, der einem Programm übergeben wird. Bei den meisten Problemen steigt die Ausführungszeit eines Programms mit der Größe des Datensatzes. Gleichzeitig können zu kompakte Darstellungen (möglicherweise unter Verwendung von Komprimierungstechniken) die Ausführung eines Programms unnötig verlangsamen. Es ist überraschend schwierig, die optimale Art der Kodierung einer Instanz zu bestimmen, denn Probleme treten in der realen Welt auf und müssen in eine geeignete Darstellung übersetzt werden, damit sie von einem Programm gelöst werden können.

Bei der Bewertung eines Algorithmus wollen wir so weit wie möglich davon ausgehen, dass die Kodierung der Probleminstanz nicht ausschlaggebend dafür ...