External_Memory_Algorithmus
External_Memory_Algorithmus

=== Definition ===
Das Modell besteht aus einem ''internen Speicher'' welcher  Datenelemente fasst, sowie einem unbegrenzten ''externen Speicher'' welcher aus  Festplatten besteht. Der wesentliche Performance-Indikator ist die I/O-Komplexität: die Anzahl von Zugriffen auf den externen Speicher zur Lösung eines Problems mit  Datenelementen. Bei jedem Zugriff auf den externen Speicher kann von jeder der  Festplatten ein Block von  Datenelementen in den internen Speicher geladen werden. Analog kann vom internen in den externen Speicher geschrieben werden. Des Weiteren soll gelten  sowie .Zwei Dateien A und B der Größe  welche im striping Verfahren auf die Festplatten D1 bis D3 verteilt sind.
Bei  Festplatten müssen für eine effiziente Verarbeitung die Eingabedaten des Problems im ''striped'' (en) Format auf den  Platten verteilt vorliegen (siehe die nebenstehende Abbildung für ein Beispiel). Die Ausgabe des Algorithmus soll dem gleichen Format folgen. Hierdurch können  Datenelemente mit der optimalen Anzahl von  I/Os in den externen Speicher geschrieben oder von ihm gelesen werden.
Oft können die Formeln der resultierenden Anzahl von I/Os vereinfacht werden, wenn statt der oben verwendeten Größen in Anzahl von Datenelementen die jeweilige Größe in Anzahl von Blöcken verwendet werden. Hieraus ergeben sich die abgeleiteten Größen  sowie .