Firmennamen suchen in linearer Zeit und mit konstantem Speicher

Neue Frage »

Auf diesen Beitrag antworten »
Moeki Firmennamen suchen in linearer Zeit und mit konstantem Speicher

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.
 
Auf diesen Beitrag antworten »
Tobias

Zuerst einmal muss man feststellen, was hier die charakteristische Größe ist, nach der man die Laufzeitkomplexität bestimmen will. Sagen wir mal n sei die Größe der Datei (= Anzahl vorhandener Einträhe).


1.) Dein Suchalgorithmus ist natürlich [latex]\mathcal{O}(n)[/latex]
Wären hier die Einträge sortiert, könntest du den gesamten Algo beschleunigen.

2.) Die Anzahl der möglichen Firmennamen mit 5 Buchstaben ist nach oben beschränkt. Sei [latex]\Sigma[/latex] das endliche Alphabet aus dem die Namen gebildet werden. Dann ist die obere Schranke für alle Firmennamen [latex]|\Sigma|^5[/latex]. Das kann man natürlich als konstant betrachten, indem man anführt, dass es nur 26 Buchstaben gibt (hier ohne Berücksichtigung der Groß-/Kleinschreibung). [latex]26^5 = \mathcal{O}(1)[/latex].

Insgesamt also [latex]\mathcal{O}(n)[/latex] aber mit großer Konstanten.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »