Waarom is invoegen beter dan snel sorteren voor een kleine lijst met elementen?

Isnt Insertion sort O(n^2) > Quick sort O(nlogn)...so for a small n, wont the relation be the same?

18

5 antwoord

Big-O Notatie beschrijft het beperkende gedrag wanneer n groot is, ook bekend als asymptotisch gedrag. Dit is een benadering. (Zie http://en.wikipedia.org/wiki/Big_O_notation )

Invoegtypen is sneller voor kleine n omdat Quick Sort extra overhead heeft vanwege de recursieve functieaanroepen. Insertion sort is ook stabieler dan Quick sort en vereist minder geheugen.

Deze vraag beschrijft enkele andere voordelen van invoegtypen. ( Is er ooit een goede reden om invoegsortering te gebruiken? )

19
toegevoegd
Sorry, ik denk niet dat snel sorteren meer geheugen vereist. Dit antwoord is verkeerd.
toegevoegd de auteur SmallChess, de bron
@SmallChess, natuurlijk. In een keer zou het logN aantal recursieve stapels nodig zijn.
toegevoegd de auteur Oorja, de bron

Definieer "klein".

Bij het benchmarken van sorteeralgoritmen kwam ik erachter dat het overschakelen van quicksort naar invoegtypen - ondanks wat iedereen zei - eigenlijk de prestaties (recursieve quicksort in C) schadelijk maakt voor arrays groter dan 4 elementen. En die arrays kunnen worden gesorteerd met een op grootte afhankelijk optimaal sorteeralgoritme.

Dat gezegd hebbende, onthoud altijd dat O (n ...) alleen het aantal vergelijkingen is (in dit specifieke geval), niet de snelheid van het algoritme. De snelheid hangt af van de implementatie, e. als uw quicksort al dan niet recursief werkt en hoe snel functieaanroepen worden afgehandeld.

Last but not least, grote oh notatie is slechts een bovengrens.

Als algoritme A 10000 n log n vergelijkingen vereist en algoritme B 10 n ^ 2 vereist, is de eerste O (n log n) en de de tweede is O (n ^ 2) . Niettemin zal de tweede (waarschijnlijk) sneller zijn.

10
toegevoegd
Voor nieuwsgierigen is de O (N ^ 2) één sneller dan de O (N Log N) één tot ongeveer N = 9000 inschrijvingen of zo.
toegevoegd de auteur sarnold, de bron
@Dennis: Controleer Wolfram Alpha . Of echo "10000 * 9000 * l (9000); 10 * 9000 * 9000" | bc -l .
toegevoegd de auteur sarnold, de bron
@Dennis: geen wonder! :) Nog een herinnering dat het zelfs in reacties helpt om precies te zijn ...
toegevoegd de auteur sarnold, de bron
@sarnold: Dat zijn 20.000.000 versus 100.000 vergelijkingen. Echt niet.
toegevoegd de auteur Dennis, de bron
@CaseyRobinson: Nee. Het karakteriseert het asymptotische gedrag niet, het beschrijft het alleen. Elk O (n ^ 2) algoritme is bijvoorbeeld ook automatisch O (n ^ 3) . En f (n) = O (n ^ 2) betekent dat er zo k is dat | f (n) | <= k n ^ 2 . Dat is een boordeling.
toegevoegd de auteur Dennis, de bron
@sarnold: Mijn slecht. Ik dacht dat je het had over quicksort en insertion sort.
toegevoegd de auteur Dennis, de bron
@CaseyRobinson: uit dezelfde alinea van hetzelfde artikel: Een beschrijving van een functie in termen van grote O-notatie levert meestal alleen een bovengrens op voor de groeisnelheid van de functie.
toegevoegd de auteur Dennis, de bron
Big Oh-notatie is geen bovengrens. Het karakteriseert het asymptotische gedrag van een functie.
toegevoegd de auteur Casey Robinson, de bron
@Dennis From Wikipedia "Big O-notatie kenmerkt functies volgens hun groeipercentages" en.wikipedia.org/wiki/ Big_O_notation
toegevoegd de auteur Casey Robinson, de bron
@Dennis We zeggen hetzelfde en discussiëren over semantiek.
toegevoegd de auteur Casey Robinson, de bron

O() - notatie wordt meestal gebruikt om de prestaties te karakteriseren voor grote problemen, terwijl opzettelijk constante factoren en additieve verschuivingen worden genegeerd voor prestaties.

Dit is belangrijk omdat constante factoren en overhead sterk kunnen variëren tussen processors en tussen implementaties: de prestaties die u krijgt voor een Basic Basic-programma op een 6502-machine zullen sterk verschillen van hetzelfde algoritme dat is geïmplementeerd als een C-programma dat op een Intel i7 wordt uitgevoerd -klasse processor. Merk op dat implementatie-optimalisatie ook een factor is: aandacht voor detail kan u vaak een grote prestatieverbetering opleveren, zelfs als alle andere factoren hetzelfde zijn!

De constante factor en overhead zijn echter nog steeds belangrijk. Als uw toepassing ervoor zorgt dat N nooit erg groot wordt, komt het asymptotische gedrag van O (N ^ 2) vs. O (N log N) niet in het spel.

Insertion sort is eenvoudig en, voor kleine lijsten, is het over het algemeen sneller dan een vergelijkbaar geïmplementeerde quicksort of mergesort. Dat is de reden waarom een ​​praktische soortimplementatie in het algemeen zal terugvallen op zoiets als invoegtypen voor het "basisscenario", in plaats van helemaal terug te gaan naar afzonderlijke elementen.

4
toegevoegd

Its a matter of the constants that are attached to the running time that we ignore in the big-oh notation(because we are concerned with order of growth). For insertion sort, the running time is O(n^2) i.e. T(n)<=c(n^2) whereas for Quicksort it is T(n)<=k(nlgn). As c is quite small, for small n, the running time of insertion sort is less then that of Quicksort.....

Hoop dat het helpt...

3
toegevoegd

Hoe zit het met binaire invoeging sorteren? Je kunt absoluut de positie zoeken om te wisselen door binaire zoekopdrachten te gebruiken.

0
toegevoegd
positie om te wisselen is een misverstand: positie om in te voegen , en daar moet je ruimte voor vrijmaken. Meestal is "array" impliciet: u moet elk item verplaatsen naar een kant van " de positie". Waarschijnlijk hebt u sleutels van items gelezen "aan de andere kant van de positie" tijdens binaire zoekopdrachten die niet zouden zijn aangeraakt met behulp van lineair zoeken: schadelijk voor toegang op kritieke paden.
toegevoegd de auteur greybeard, de bron
Ik denk dat [binair vinden van het invoegpunt] meer [efficiënter] is dan O (n) - wordt gedomineerd door de "array-kopie" , lagere constante voor bulkcopy of niet.
toegevoegd de auteur greybeard, de bron
Mee eens. Dat is de wisselwerking. Je moet in deze situatie kiezen. Als u binaire zoekopdrachten gebruikt, verlaagt u de stappen en krijgt u snel de positie om in te voegen, maar hebt u meer ruimte nodig om de "array-kopie" te doen. Slechtste geval nog steeds lineaire tijd, maar gemiddeld vind ik het effectiever dan O (n)
toegevoegd de auteur Phát Phát, de bron