8

PI (Fach) / Suche (Lektion)

Diese Lektion wurde von blace erstellt.

Lektion lernen

Diese Lektion ist leider nicht zum lernen freigegeben.

zurück  |  weiter 1 / 1

• Wie funktioniert binäre Suche? Die Vorrausetzungen für die binäre Suche ist, dass in einem Array(oder array-ähnlichem also etwas mit Direktzugriff) gesucht wird, das eine ordnungsrelation für die Elemente definiert ist und, dass das Array sortiert ist. Dann wird nach dem divide and conquer prinzip gearbeitet und so Sortiert, dass nicht jedes Element geprüft werden muss. Wir haben ein Array und suchen einen key. bottom = 0 top = länge des Arrays solange bottom +1 != top ist: mid:= (top+bottom)/2 falls array[mid] >key    top = mid sonst    bottom = mid
• Wie hoch ist der Aufwand bei binärer Suche in einem sortierten Array? Der Aufwand liegt bei O(log n)
• Wie hoch ist der Aufwand bei linearer Suche in einem beliebigen Array oder einer beliebigen Liste? Der Aufwand liegt bei O(n)
• Erläutere die Arbeitsweise einer selbstanordnenden Liste, die nach dem Prinzip Frequency-Count arbeitet. Eine Selbstanordnende Liste mit dem Prinzip Frequency Count arbeitet, stellt Elemente die Häufigeer gesucht werden an den Anfang der Liste, dies tut sie mittels eines Zählers in jedem Listenknoten, der bei jedem Fund des Elementes um 1 erhöht wird. Sollte nun dieser Zähler höher als der des Vorgänger Elementes werden, so wird das Element entnommen und erneut eingefügt, das Einfügen funktioniert, indem sich die Liste immer das Element le mekrt , bei dessen Nachfolger es einen Häufigkeitsabfall gibt und das gefundene Element einfach hinter le einfügt. Sollte es keinen Häufigkeitsabfall geben, so wird das Element ganz vorne eingefügt und ein nicht vorhandenen Element wird an das Ende der Liste angehängt.
• Erläutere die Arbeitsweise einer selbstanordnenden Liste, die nach dem Prinzip Transpose arbeitet. eine Selbstanordnende Liste, die nach dem transpose Prinzip arbeitet, arbeitet wie eine Naive Liste, jedes Neue Element wird an den Anfang der Liste eingefügt, abertauscht jeden gefundenen Eintrag mit seinem Vorgänger, also wird um eine Stelle näher zum Listenanfang geschoben.
• Erläutere die Arbeitsweise einer selbstanordnenden Liste, die nach dem Prinzip Move-to-Front arbeitet. Eine Selbstanordnende Liste arbeite wie eine Naive Liste, neue Elemente werden an den Anfang eingefütg, aber jeder gefundene Eintrag wird entnommen und an den Anfang eingefügt.
• Wie arbeiten selbstanordnende Listen? Selbsanordnende Listen Suchen eine lineare Liste von Anfang bis Ende durch und platzieren häufiger gesuchte Elemente weiter nach vorne, mittels einem der drei Ansätze MF(move to front) T(transpose) FC(frequency count)
• Wie funktioniert Interpolationssuche? Die Interpolationssuche funktioniert ähnlich wie die binäre Suche, nur dass statt nach dem nächsten element mittels mid = bottom+1/2(top+bottom), nach einem Zuäflligen Element gesucht wird, indem 1/2 durch eine Schätzung ersetzt wird mid = bottom+ key-a[bottom]/a[top]-a[bottom] (top-bottom)

zurück  |  weiter 1 / 1