Informatiker Board | Druckvorschau: Firmennamen suchen in linearer Zeit und mit konstantem Speicher

Geschrieben von Moeki am 20.01.2007 um 13:30:

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.

Geschrieben von Tobias am 20.01.2007 um 14:30:

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.