Tidskompleksiteten af QuickSort, når det første element vælges som drejebilledet er:
* worst-case:o (n^2)
* Bedst sag:O (n log n)
* Gennemsnitlig sag:O (n log n)
Forklaring:
* worst-case:o (n^2)
Dette sker, når inputarrayet allerede er sorteret (enten i stigende eller faldende rækkefølge) eller næsten sorteret. Når arrayet er sorteret, vil pivoten altid være det mindste (eller største) element. Dette resulterer i meget ubalancerede partitioner.
For eksempel, hvis matrixen er sorteret i stigende rækkefølge, og det første element er altid omdrejningspunktet:
1. Det første element vælges som pivot.
2. Alle andre elementer er større end pivoten, så de ender alle i den rigtige partition.
3. den venstre partition er tom.
4. det rekursive opkald foretages derefter på en underordning af størrelse `N-1 '.
Denne proces gentages, hvilket fører til en rekursionsdybde på `n`. På hvert niveau 'Jeg' af rekursionen udfører vi 'n - jeg' sammenligninger. Det samlede antal sammenligninger bliver omtrent `n + (n-1) + (n-2) + ... + 1`, som er lig med` n (n + 1)/2 ', som er o (n^2).
* Bedst sag:O (n log n)
Det bedste tilfælde sker, når pivoten konsekvent deler matrixen i to lige (eller næsten lige) halvdele. I denne situation bliver rekursionsdybden `log n`, og på hvert niveau udfører vi` n 'sammenligninger, hvilket resulterer i en tidskompleksitet på `O (n log n)`.
* Gennemsnitlig sag:O (n log n)
I gennemsnit fungerer Quicksort meget godt. Når pivot -valget konsekvent producerer rimeligt afbalancerede partitioner, er tidskompleksiteten `O (n log n)`. Den "gennemsnitlige" antager, at input er tilfældigt bestilt, og at Pivot -valget ikke er konsekvent dårligt.
Virkning af drejevalg:
Valget af Pivot påvirker Quicksorts ydeevne væsentligt. At vælge det første element som pivot er en naiv strategi og kan føre til det værste tilfælde i mange almindelige situationer.
afbødningsteknikker:
For at undgå det værste tilfælde, når du bruger QuickSort, er det vigtigt at vælge en god drejning. Her er nogle almindelige teknikker:
* Tilfældig pivot: At vælge et tilfældigt element som pivot er en enkel og effektiv måde at undgå det værste tilfælde. Dette gør algoritmen's præstation mindre afhængig af den indledende rækkefølge af input.
* median-of-tre: Vælg medianen af den første, midterste og sidste elementer i matrixen som drejning. Dette giver ofte en bedre drejning end blot at vælge det første element.
* Andre drejevalgsstrategier: Der er mere sofistikerede drejepunktionsstrategier, men de tilføjer ofte overhead, der opvejer deres fordele for typiske brugssager.
Kortfattet:
Brug af det første element som drejning i QuickSort kan være en dårlig strategi, især hvis inputarrayet sandsynligvis vil blive sorteret eller næsten sorteret. Det er bedst at bruge Pivot Selection Strategies, der forsøger at producere mere afbalancerede partitioner for at sikre, at algoritmen fungerer tættere på sin gennemsnitlige sag `O (n log n)` tidskompleksitet.
