Ich habe kürzlich einen Sortieralgorithmus geschrieben. Ich habe den Link zum Code sowie ein Beispiel hier angeführt: Sortieralgorithmus
Da mein Mathe-Hintergrund knapp ist, bin ich esneugierig, was man über die Effizienz dieses Algorithmus sagen kann. Ich führte mehrere Tests durch und stellte fest, dass die Anzahl der Schritte linear zunahm, wenn die Anzahl der Elemente anstieg. Jede Hilfe würde sehr geschätzt werden.
Antworten:
0 für die Antwort № 1Dein Algorithmus scheint zu greifen erwartet O (N) Zeit an Uniform zufällig verteilten Daten. Das ist nicht so schwierig, weil Sie die Zufallsdaten problemlos in gleichmäßig beabstandete Buckets verteilen können, und sie werden von konstanter erwarteter Größe sein.
Es ist auch nicht dasselbe wie O (N) für beliebige Daten, was für eine vergleichsbasierte Sortierung unmöglich ist. O (N) Zeit Sortierung von Ganzzahlen mit begrenzter Größe ist möglich mit einer Radix-Sortierung jedoch. Sehen: https://en.wikipedia.org/wiki/Radix_sort
Nach kurzem Blick auf Ihren Algorithmus, IIch glaube, dass ein Gegner systematisch eine Eingabe wählen könnte, die Ihren Algorithmus zwingt, O (N ^ 2) zu nehmen. Das würde dir einen O (N ^ 2) -Algorithmus machen.