Suche nach dem max.Element < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo alle zusammen,
Ich bräuchte euere Ratschläge bei der Lösung des folgenden Problems:
Es besteht eine Reihenfolge der Ganzzahlen 0,1,2,
.,y,
,N, wo N ein unbekanntes maximales Element ist.
Diese Reihenfolge wird als ein Teil des Namens (also ein Index) benutzt.
Die Aufgabe besteht darin, ein um 1 größer als N Element zu finden. Es wurde zuerst bei der Suche nach N+1 ein schlichtes sequentielles Verfahren eingesetzt. (Also das Inkrementieren um 1 des aktuellen Elementes y , wenn schon y-1 existiert. Aus bestimmten Gründen führt die Abfrage auf die Existenz des Elementes ab der gewissen Anzahl der Elemente der Reihenfolge zu nicht akzeptablen zeitlichen Abfrageintervallen.
Daher wurde entschieden, den Such-Algorithmus zu optimieren. Die Effizienz eines Suchalgorithmus wird über die Anzahl der Zugriffe auf Reihenfolge gemessen, die bis zum Erreichen des N+1 nötig sind.
Die Idee ist, die Reihenfolge aufzuteilen auf s.g. Fenster (Z.B [0,x), [x,y), [y,z),
,[r,M], wo M ist die höchste Grenze bei der Suche, bei deren Erreichen, die Suche wird aufgehört ohne Erfolg.
Offene Fragen:
Welcher Algorithmus sollte man bei der Suche innerhalb der Intervalle einsetzen? (Z.B würde Quadratische Binärsuche passen?)
Welcher Algorithmus sollte man bei der Berechnung der Grenzen fürs Fenster anwenden?
Mag sein, daß ihr wohl bessere Ideen für die Losung habt, - ich bedanke mich dafür
cu.
Udo
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:14 Mo 19.02.2007 | | Autor: | Karl_Pech |
Hallo Udo,
Müßte man zur Beantwortung deiner Frage nicht erstmal wissen auf welcher Datenstruktur ihr die Suche durchführt? Verschiedene Datenstrukturen bieten verschiedene Suchmöglichkeiten.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:20 Mi 21.02.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
