Die besten
Sortierverfahren benötigen im ungünstigsten Fall n*log(n) Schritte. Hinzu kommen n Vergleiche zur Überprüfung auf Duplikaten. Diese Verfahrenskette benötigt also rund n*log(n)+n Schritte.
Die Effizienz des Find-Algorithmuses liegt unter Voraussetzung einer sortierten Liste bei maximal log(n)/log(2) Schritten. Die Find Funktion wird n mal aufgerufen und zwar auf eine Liste deren Elementenzanzahl von 1 bis n ansteigt. Daraus ergeben sich log(n!)/log(2) Schritte für diese Verfahrenskette.
So und nun müsste man noch wissen was kleiner ist: n*log(n)+n oder log(n!)/log(2)
Durch empirische Erhebungen (=Ausprobieren
) habe ich herausgefunden, dass Methode2 rund doppelt soviele Schritte braucht wie Methode1 ... hätte ich ehrlich gesagt nicht erwartet, aber es ist ja auch nicht gesagt das mein Beweis fehlerfrei ist
