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.

Ich bin mir nicht sicher, ob der konstante Speicher auf die Datei bezogen ist. Ich glaube eher der Speicherverbrauch des Programms ist gemeint. Wird das Programm so realisiert, daß immer nur 2 Firmennamen im Speicher liegen (der generierte und der zu vergleichende aus der Datei), dann ist der Speicherverbrauch konstant.

Ich denke auch, daß der beschriebene Algorithmus linearer Ordnung ist, da er ja für jeden neu generierten Namen nochmal die Datei durchackert.

Ideal dafür wäre ein Indexed Trie oder Linked Trie

das lineare Durchackern ist da ziemlich sinnlos.

Indexed/Linked Trie würde auch das Finden von Alternativen wesentlich effizienter machen.

Alles, was die Daten in sortierter Form liefern kann, sei es ein Index oder ein sortierender Container, würde den Suchvorgang auf lineare Laufzeit verkürzen. Das Erstellen eines Index bzw. das Sortieren selbst ist aber O(n * log n). Wenn man den Index persistent halten kann oder die Daten sortiert wieder ablegt, hat man den Aufwand natürlich nur einmal.

@Moeki,

Dein Algorithmus ist nicht linear. Im Worst Case (nur ZZZZZ ist noch frei, und danach suchst du zuletzt) hast du quadratische Laufzeit. Wie wahrscheinlich dieser Worst Case ist, hängt aber davon ab, wie voll die Liste ist.

Ich denke, dass das File bereits sortiert ist. Bzw. ich kann es ja darauf beschränken bzw. die Laufzeit für das Sortieren ausser Acht lassen.

Mit dem Worst Case stimmt-

Wenn die Daten sortiert sind, musst du nur der Reihe nach jeden Eintrag mit seinem Nachfolger vergleichen und prüfen, ob dazwischen eine "Lücke" ist. Das geht in O(n).

Sowas habe ich mir auch schon gedacht, aber dann müsste ich die Firmennamen ja irgendwie in eine numerische, vergleichbare Skala übertragen? Oder wie sollte man sonst "Lücken" erkennen?

Für Buchstaben geht das sicher, aber nicht für Wörter?

Oder ich addiere jeweils die ord(Substring, 1(2,3,4,5)) der Wörter und vergleiche mit dem nächsten?

Dann weiß ich zwar, dass ne Lücke ist, aber keinen entsprechenden freien Namen.

Bezüglich Linked/Indexed Trie: Das ist doch nicht mehr mit konstantem Speicherbedarf verbunden.

Sowas habe ich mir auch schon gedacht, aber dann müsste ich die Firmennamen ja irgendwie in eine numerische, vergleichbare Skala übertragen?

Prinzipiell brauchst du nichts zu übertragen, der Name ist ein numerischer, vergleichbarer Wert. Die erlaubten Zeichen bilden die Ziffern, die Anzahl der erlaubten Zeichen ist die Basis der Darstellung.

Wenn du z.B. nur Großbuchstaben erlaubst, ist ein Name die Darstellung einer Zahl zur Basis 26. Du kannst ein A als 0 interpretieren, und ein Z als 25. Damit hätte AAAAA den Wert 0 und ZZZZZ den Wert 25 * 26^4 + 25 * 26^3 + 25*26^2 + 25*26 + 25 = 11.881.375.

Oder ich addiere jeweils die ord(Substring, 1(2,3,4,5)) der Wörter und vergleiche mit dem nächsten?

Einfaches Addieren reicht nicht. Das ist nicht eindeutig. Jede "Stelle" hat eine andere Wertigkeit, eben wie bei Zahlensystemen.