Groß-O-Notation, gängige Sortier- und Suchalgorithmen sowie Rekursionsmuster, wie sie in technischen Vorstellungsgesprächen und Lehrveranstaltungen geprüft werden.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- Was misst die Groß-O-Notation?
Show answer
Wie der Laufzeit- oder Speicherbedarf eines Algorithmus mit wachsender Eingabegröße zunimmt.- Definiere die Zeitkomplexität O(1).
Show answer
Konstante Zeit; die Laufzeit ändert sich unabhängig von der Eingabegröße nicht.- Definiere die Zeitkomplexität O(n).
Show answer
Lineare Zeit; die Laufzeit wächst proportional zur Eingabegröße n.- Definiere die Zeitkomplexität O(log n).
Show answer
Logarithmische Zeit; die Laufzeit wächst mit dem Logarithmus der Eingabegröße.- Definiere die Zeitkomplexität O(n^2).
Show answer
Quadratische Zeit; die Laufzeit wächst mit dem Quadrat der Eingabegröße.- Definiere die Zeitkomplexität O(n log n).
Show answer
Linearithmische Zeit; die Laufzeit entspricht n mal dem Logarithmus von n.- Definiere die Zeitkomplexität O(2^n).
Show answer
Exponentielle Zeit; die Laufzeit verdoppelt sich mit jeder Erhöhung der Eingabegröße um 1.- Wie hoch ist die Zeitkomplexität beim Zugriff auf ein Array-Element über den Index?
Show answer
O(1), konstante Zeit.- Wie hoch ist die Zeitkomplexität beim Durchsuchen eines unsortierten Arrays nach einem Wert?
Show answer
O(n), lineare Zeit.- Wie hoch ist die Zeitkomplexität der binären Suche in einem sortierten Array?
Show answer
O(log n), logarithmische Zeit.- Was muss für ein Array gelten, bevor die binäre Suche eingesetzt werden kann?
Show answer
Das Array muss sortiert sein.- Wie hoch ist die Zeitkomplexität beim Einfügen eines Elements am Anfang eines Arrays?
Show answer
O(n), lineare Zeit.- Wie hoch ist die Zeitkomplexität beim Anhängen eines Elements an ein dynamisches Array mit freier Kapazität?
Show answer
O(1) amortisiert, konstante Zeit.- Wie hoch ist die durchschnittliche Zeitkomplexität beim Suchen in einer Hashtabelle?
Show answer
O(1), konstante Zeit, bei einer guten Hashfunktion.- Wie hoch ist die Zeitkomplexität von Quicksort im Durchschnittsfall?
Show answer
O(n log n), linearithmische Zeit.
FlashKeepers