Available inGermanEnglishFrenchHindiPortugueseRussianSpanish
Big-O und Datenstrukturen für Interviews
Nenne die Zeit- und Platzkosten jeder Operation auf Array, verketteter Liste, Hash-Map, Baum, Heap oder Trie, inklusive des amortisierten Falls, und begründe sie laut. Für alle, die sich auf ein Coding-Interview oder eine Data-Structures-Klausur vorbereiten, Schleifen und Hash-Maps kennen, eine Big-O-Antwort bisher aber nur wiedererkennen statt sie herzuleiten. Vierundfünfzig Karten in sieben Kapiteln; algorithmische Muster deckt Coding-Interview-Muster (Blind 75) ab.
Ein Programm mit Kosten n^2 braucht für 1.000 Elemente eine Sekunde. Schätze die Zeit für 2.000 Elemente.
Etwa 4 Sekunden
— Verdopple die Eingabe und quadriere die Verdopplung.
Source
Eine Verdopplung von n vervierfacht quadratische Kosten, denn (2n)^2 = 4n^2; die zehnfache Eingabe kostet das Hundertfache. Dieser Verhältnistrick beantwortet „und wenn die Eingabe wächst?“ ohne eine einzige Konstante: Du brauchst nie die Geschwindigkeit der Maschine, nur die Form des Wachstums. Merke ihn zusammen mit seinen Gegenstücken: Bei O(n log n) wird aus einer Verdopplung etwas mehr als die doppelte Zeit, bei O(log n) genau ein Schritt mehr.