Algorithmen lernen

Kapitel 8. Einpacken

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

Mein Ziel in diesem Buch war es, dich mit den grundlegenden Algorithmen und den wichtigsten Datentypen der Informatik vertraut zu machen. Du musst wissen, wie du die folgenden Datentypen effizient implementieren kannst, um die Leistung deines Codes zu maximieren:

Tasche

Eine verkettete Liste garantiert O(1) Leistung beim Hinzufügen eines Wertes. Wenn du dich für ein Array entscheidest, musst du die Größe des Arrays geometrisch vergrößern, um eine amortisierte O(1) Leistung über die durchschnittliche Nutzung zu garantieren (obwohl du immer noch eine O(N)-Laufzeitleistung bei den seltenen Größenänderungen haben wirst). Beachte, dass ein Bag in der Regel nicht zulässt, dass Werte entfernt werden, und auch nicht verhindert, dass doppelte Werte hinzugefügt werden.

Stack

Eine verkettete Liste kann die Werte in einem Stapel speichern, so dass push() und pop()eine O(1)-Laufzeitleistung haben. Der Stack zeichnet die top des Stacks auf, um Werte zu pushen und zu popen.

Warteschlange

Eine verkettete Liste kann eine Warteschlange effizient speichern, so dass enqueue() unddequeue() eine O(1)-Laufzeitleistung haben. Die Warteschlange speichert den first und den last Knoten in der verketteten Liste, um effizient Werte zur Warteschlange hinzuzufügen und aus ihr zu entfernen.

Symboltabelle

Der offene Adressierungsansatz für Symboltabellen ...