3.1 Hintergrund: der Speicherplatz im Rechner

Um überhaupt ein Gefühl für die Problematik zu bekommen, müssen wir zumindest im Prinzip verstehen, wie der Speicher eines Rechners organisiert sind. Bei der binären Suche beispielsweise sind wir ja davon ausgegangen, dass man mit einer Code-Zeile wie

c = array[i];

in einem Schritt die \(i\)-te Zelle des Arrays auslesen kann. Ist dies eine vernünftige Annahme? In sehr alten Rechnern wahrscheinlich nicht: der externe Speicher war ein Magnetband; um an die \(i\)-te Zelle zu gelangen, muss man erst einmal dort hinspulen; wenn wir Pech haben, ist \(i\) weit weg. Auch bei Festplatten (Hard disk drives, HDD) spielt die physische Anordnung eine Rolle: der Lesekopf muss die entsprechende Spur finden, und dann abwarten, bis die Platte sich an die richtige Stelle rotiert hat. Moderne Rechner (Stand 2023) verwenden allerdings eher Solid-State-Drives (SSD), die ohne bewegliche Teile auskommen. Für sie ist die Annahme einer festen, konstanten Zugriffszeit realistischer. Wenn die Zugriffszeit auf Zellen in unserem Speicher unabhängig von dem "Aufenthaltsort" der Zelle ist, sprechen wir von einem Random Access Memory (RAM).

Stellen wir uns das RAM als großes Array aus \(N\) Zellen vor: Mem[0...N-1]. Es unterstützt Lese- und Schreiboperationen der Art

write <data> <address>                            
read <address>