|
|
Gegeben sei ein sequentielles File, in dem N≤10.000.000 Firmennamen mit je max. fünf Buchstaben gespeichert sind. Ich möchte einen Algrithmus entwerfen, der in linearer Zeit und mit konstantem Speicher einen nicht vorhandenen Firmennamen findet.
Zunächst lasse ich beginnend von der kleinsten Kombinationsmöglichkeit einen Firmennamen erstellen. Dann öffne ich das File und mache solange get(f), bis (1) das Ende des Files erreicht ist bzw. (2) der Firmenname gefunden wurde. Bei (1) habe ich einen nicht genutzten Firmennamen gefunden. Bei (2) muss ich den nächstmöglichen Firmennamen erstellen und das File erneut durchsuchen.
Konstant sollte das sein, weil am File nichts geändert wird. Aber doch nicht linear oder?
Gruß,
Moeki.
|
|
