nicht angemeldet
Tag,
Es soll die relative Geschwindigkeit zweier Algorithmen gezeigt werden, weswegen ich ein paar Optimierungen vornehmen möchte. Zeit habe ich also schon, mich interessieren lediglich die Verhältnisse.
nur aus Interesse: Sind beide Algorithmen von <http://de.wikipedia.org/wiki/Komplexit%C3%A4t_%28Informatik%29title=@gleicher Komplexität>? Was hast Du genau vor? Willst Du z.B. das Verhalten empirisch ermitteln und demonstrieren?
Teilweise, es geht um Sortieralgorithmen. Die getesteten sind Bubblesort, Insertion sort und Selection sort mit O(n^2), Quicksort mit O(n log n) und mein Bitsort mit O(n). Daher auch hier die Bitfrage. Ein Test gerade hat ergeben (der jeweils zweite Wert bezieht sich auf die Sortierung der bereits sortierten Liste, d.h. den best case):
3000 Zufallszahlen: 0.0158278942108 Sekunden.
Bubblesort: 12.5058748722 Sekunden.
Bubblesort: 7.46138906479 Sekunden.
Insertion sort: 13.6109161377 Sekunden.
Insertion sort: 9.9717400074 Sekunden.
Selection sort: 10.0230801105 Sekunden.
Selection sort: 7.15000391006 Sekunden.
Quicksort: 0.545024871826 Sekunden.
Quicksort: 0.522994041443 Sekunden.
Bitsort: 0.0652689933777 Sekunden.
Bitsort: 0.0693278312683 Sekunden.
Die Zufallszahlen waren jeweils dieselben. PHP ist hier sicher nicht die optimale Wahl, reicht aber, um die Komplexitätsunterschiede zu zeigen.
Bye,
Peter
Der Martin