|
|
|
Für die Aufwandsanalyse
orientieren wir uns am C-Programm. |
 |
- Die i-Schleife wird (n-1)-mal
durchlaufen.
- Beim i-ten Durchlauf wird die j-Schleife (n - (i+1)) = (n-i-1)-mal
durchlaufen.
- Dabei erfolgt jeweils ein
Schlüsselvergleich.
Die Gesamtzahl der Schlüsselvergleiche ist also unabhängig von
den Schlüsseln der Datensätze:
|
|
|
 |
- Die i-Schleife wird (n-1)-mal
durchlaufen.
- Pro Durchlauf der i-Schleife werden 4 Umspeicherungen
durchgeführt (zzgl. denen der j-Schleife).
- Die j-Schleife wird (n-i-1)-mal
aufgerufen.
- Der if-Zweig innerhalb der j-Schleife wird dabei
- im besten Fall nie
- im schlechtesten Fall immer
- im Mittel jedes zweite Mal
durchlaufen. Dabei erfolgt jeweils eine
Umspeicherung, also insgesamt
- im besten Fall 0
- im schlechtesten Fall n-1-i
- im Mittel (n-1-i)/2
Umspeicherungen.
Also:
|
|
|
