Laufzeit von Algorithmen abschätzen

Deine Frage ist jetzt konkret was?

- Bietet sich für den Vgl. eine bestimmte Entwicklungsumgebung an? (das 
Betriebssystem und Prozesse im Hintergrund sollen das Ergebnis nicht 
stark beeinflussen)
- Ist das Vorgehen nachvollziehbar bzw. führt es auf ein 
aussagekräftiges/allgemeingültiges Ergebnis?
- Gibt es Alternativen zum vorgeschlagenen Vorgehen?

WiInfor schrieb:
> - Bietet sich für den Vgl. eine bestimmte Entwicklungsumgebung an?

Diejenige, die Du am besten beherrscht. Muß nur für alle 
Implementationen exakt dieselbe sein, bis hin zur identischen 
Compilerversion und Compileroptionen.

Ach ja, und bei Quicksort nicht den C-Library-qsort nehmen, weil der für 
jeden Vergleich und jeden Tausch einen extra Funktionsaufruf machen muß, 
der nicht inlined werden kann, so daß das Ergebnis dann verzerrt wird.

> (das
> Betriebssystem und Prozesse im Hintergrund sollen das Ergebnis nicht
> stark beeinflussen)

Unter Linux kannste Dir die reine CPU-Zeit ausgeben lassen, die Dein 
Prozeß verbraucht hat. Damit sind Betriebssystem und andere laufende 
Anwendungen egal.

> - Ist das Vorgehen nachvollziehbar

Finde ich schon.

> bzw. führt es auf ein
> aussagekräftiges/allgemeingültiges Ergebnis?

Nicht unbedingt. Denn wie "gut" Algorithmen sind, hängt von einigen 
Randbedingungen ab:

- Welche Größenordnung der Listenlänge ist von Interesse?
Beispielsweise ist Quicksort bei kurzen Listen (unter 100) schlecht, 
weil der Overhead zu stark ist.
Die O-Notation ist nur von Belang für große Listenlängen und drückt im 
Wesentlichen nicht aus, wie schnell ein Algorithmus ist, sondern wie gut 
er mit wachsender Listenlänge skaliert. Der konstante Faktor, der bei 
der O-Notation weggelassen wird, ist für verschiedene Algorithmen 
nämlich auch unterschiedlich.

- Wie ist der Aufwand eines Vergleiches im Verhältnis zu einem Tausch?
Es gibt Algorithmen, die möglichst wenig Tauschaktionen machen, dafür 
aber mehr Vergleiche. Das rechnet sich nur, wenn der Tausch wirklich 
aufwendiger ist.
Also beispielsweise, wenn die Elemente sagen wir mal structs mit 64 Byte 
sind, während der Vergleichsschlüssel nur ein 4 Byte Integer ist.
Hast Du hingegen als Elemente eine Union aus einem 4-Byte-Integer, den 
Du auf einen Schlag kopieren kannst, und der Vergleichsschlüssel ist 
eines der Bytes der Union, dann ist ein Vergleich genauso aufwendig wie 
ein Tausch.

- Was auch noch berücksichtigt werden sollte: Braucht der Algorithmus 
zusätzlichen Speicherplatz (temporäres Array oder, wie Quicksort, 
impliziten Stack)? Wenn ja, wieviel? Wie sind die Schwankungen der 
Laufzeit? Gibt es da gelegentlich fiese Ausreißer? Beispielsweise hat 
Heapsort eine extrem konstante Laufzeit, ist allerdings langsamer als 
Shellsort (bei kurzen Listen zumindest). Umgedreht ist Quicksort 
schwierig so zu implementieren, daß er nicht in seltenen Randfällen 
pathologische Ausreißer zeigt.

Gemessen werden sollte auf jeden Fall immer die Sortierzeit mit bereits 
vorsortierter Liste, mit invers vorsortierter Liste und mit 
Zufallszahlen. Die Zufallszahlen müssen dann aber für jeden Algorithmus 
dieselben sein. Also die zufällige Liste nach der Erzeugung einmal 
wegspeichern. Außerdem nicht nur eine Messung mit Zufallsliste machen, 
sondern viele.

Auch interessant ist, was passiert, wenn viele doppelte Einträge 
vorhanden sind. Im Extremfall 95% Nullen und nur 5% eigentlich 
ausgefüllte Felder.