TU Wien:Mathematik 2 UE (diverse)/Übungen SS07/Beispiel 142

Aus VoWi
Wechseln zu: Navigation, Suche

Beim Sortieren von n Zahlen durch "Direktes Einfügen" gilt für die Anzahl der v_n der Vergleiche (im ungünstigsten Fall)

v_1=0 und v_n = v_{n-1} + n - 1, n=2,3,\ldots

und für die Zahl w_n der Wertzuweisungen

w_1=0 und w_n = w_{n-1} + n + 1, n=2,3,\ldots

Warum? Man bestimme explizite Formeln für v_n und w_n und schätze deren Größenordnungen (in der O-Notation) ab.

Links[Bearbeiten]