Informatiker Board | Praktische Informatik | Firmennamen suchen in linearer Zeit und mit konstantem Speicher

Informatiker Board » Themengebiete » Praktische Informatik » Firmennamen suchen in linearer Zeit und mit konstantem Speicher

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Firmennamen suchen in linearer Zeit und mit konstantem Speicher

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Moeki

Grünschnabel

Dabei seit: 20.01.2007
Beiträge: 1
Herkunft: Erkner

Firmennamen suchen in linearer Zeit und mit konstantem Speicher

Zitatantwort auf diesen Beitrag erstellen

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

Nehmen Sie Moeki in Ihre Freundesliste auf

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 $[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.

20.01.2007 14:30

Nehmen Sie Tobias in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Firmennamen suchen in linearer Zeit und mit konstantem Speicher