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 » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 2 Beiträge
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.
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.