Firmennamen suchen in linearer Zeit und mit konstantem Speicher |
Moeki
Grünschnabel
Dabei seit: 20.01.2007
Beiträge: 1
Herkunft: Erkner
|
|
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.
|
|
20.01.2007 13:30 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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
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 das endliche Alphabet aus dem die Namen gebildet werden. Dann ist die obere Schranke für alle Firmennamen . 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). .
Insgesamt also aber mit großer Konstanten.
|
|
20.01.2007 14:30 |
|
|
|