Median av median

Median av medianer
Klass	Urvalsalgoritm
Datastruktur	Array
Prestanda i värsta fall
Bästa möjliga prestanda
Värsta tänkbara rymdkomplexitet	extra

Inom datavetenskap är medianen exakt för medianerna en ungefärlig medianvalsalgoritm , som ofta används för att tillhandahålla en bra pivot för en urvalsalgoritm, oftast snabbval , som väljer det k: te minsta elementet i en initialt osorterad array. Medianen av medianerna finner en ungefärlig median i linjär tid. Genom att använda denna ungefärliga median som en förbättrad pivot, reduceras värsta tänkbara komplexiteten för snabbval från kvadratisk till linjär , vilket också är den asymptotiskt optimala värsta tänkbara komplexiteten för valfri urvalsalgoritm. Med andra ord är medianen för medianerna en ungefärlig medianvalsalgoritm som hjälper till att bygga en asymptotiskt optimal, exakt generell urvalsalgoritm (särskilt i betydelsen värsta tänkbara komplexitet), genom att producera bra pivotelement.

Medianen av medianer kan också användas som en pivotstrategi i quicksort , vilket ger en optimal algoritm, med värsta tänkbara komplexitet $O(n\log n)$ . Även om detta tillvägagångssätt optimerar den asymptotiska värsta tänkbara komplexiteten ganska bra, överträffas den vanligtvis i praktiken genom att istället välja slumpmässiga pivoter för dess genomsnittliga ${\displaystyle O(n)}-$ komplexitet för urval och genomsnittlig $O(n\log n)$ komplexitet för sortering, utan någon overhead för beräkning av pivoten.

På liknande sätt används medianen av medianer i hybridintroselektalgoritmen som en reserv för pivotval vid varje iteration tills kth minsta hittas. Detta säkerställer återigen en linjär prestanda i sämsta fall, förutom linjär prestanda för genomsnittligt fall: introselekt börjar med snabbval (med slumpmässig pivot, standard), för att erhålla bra genomsnittlig prestanda och faller sedan tillbaka till modifierad snabbval med pivot som erhålls från median av medianer om framstegen är för långsam. Även om den är asymptotiskt lik kommer en sådan hybridalgoritm att ha en lägre komplexitet än en enkel introselekt upp till en konstant faktor (både i genomsnitt och värsta fall), oavsett ändlig längd.

Algoritmen publicerades i Blum et al. (1973) , och kallas därför ibland BFPRT efter författarnas efternamn. I den ursprungliga uppsatsen kallades algoritmen PICK , vilket refererar till snabbval som "HITTA".

Motivering

Quickselect är i genomsnitt linjär tid, men det kan kräva kvadratisk tid med dåliga pivotval. Detta beror på att snabbval är en dividera och erövra algoritm, där varje steg tar $O(n)$ tid i storleken på den återstående sökuppsättningen. Om sökmängden minskar exponentiellt snabbt i storlek (med en fast proportion) ger detta en geometrisk serie gånger $O(n)$ faktorn för ett enda steg, och därmed linjär total tid. Men om sökuppsättningen minskar långsamt i storlek, till exempel linjärt (med ett fast antal element, i värsta fall endast minska med ett element varje gång), så ger en linjär summa av linjära steg kvadratisk total tid (formellt triangulärt ) siffror växer kvadratiskt). Till exempel inträffar det värsta fallet när man pivoterar på det minsta elementet vid varje steg, som att tillämpa snabbval för det maximala elementet på redan sorterade data och ta det första elementet som pivot varje gång.

Om man istället konsekvent väljer "bra" pivoter undviks detta och man får alltid linjär prestanda även i värsta fall. En "bra" pivot är en för vilken vi kan fastställa att en konstant andel element faller både under och över den, eftersom sökuppsättningen då minskar åtminstone med en konstant andel vid varje steg, alltså exponentiellt snabbt, och den totala tiden kvarstår linjär. Medianen är en bra pivot – det bästa för sortering och det bästa övergripande valet för urval – vilket minskar sökningen med hälften vid varje steg. Så om man kan beräkna medianen i linjär tid, lägger detta bara till linjär tid till varje steg, och därmed förblir den övergripande komplexiteten hos algoritmen linjär.

Median-av-medianalgoritmen beräknar en ungefärlig median, nämligen en punkt som garanterat ligger mellan 30:e och 70:e percentilen (i mitten av 4 decilerna ). Således minskar sökuppsättningen med minst 30 %. Problemet reduceras till 70 % av originalstorleken, vilket är en fast andel mindre. Att tillämpa samma algoritm på den nu mindre uppsättningen rekursivt tills endast ett eller två element återstår resulterar i en kostnad på ${\frac {n}{1-0,7}}\approx 3,33{n}$

Algoritm

Som nämnts tidigare används median-av-medianer som en pivotvalsstrategi i snabbvalsalgoritmen, som i pseudokod ser ut som följer. Var noga med att hantera vänster , höger och n vid implementering. Följande pseudokod förutsätter att vänster , höger och listan använder en-baserad numrering och att select initialt anropas med 1 som argument till vänster och längden på listan som argument till höger . Observera att detta returnerar indexet för det n:e minsta talet efter omarrangering av listan, snarare än det faktiska värdet av det n:e minsta talet.

        
            
             funktion  välj(lista, vänster, höger, n)  loop  om  vänster = höger  sedan  tillbaka  vänster pivotIndex := pivot(lista, vänster, höger) pivotIndex := partition(lista, vänster, höger, pivotIndex, n)  om  n = pivotIndex  då  returnera  n  annat  om  n < pivotIndex  sedan  höger := pivotIndex - 1  annat  vänster := pivotIndex + 1

Subrutinpivot är den faktiska median-av-medianalgoritmen. Den delar upp sin inmatning (en lista med längden $n$ ) i grupper om högst fem element, beräknar medianen för var och en av dessa grupper med hjälp av någon subrutin, och beräknar sedan rekursivt den sanna medianen för ${\frac {n} {5}}$ medianer som hittades i föregående steg:. Observera att pivotsamtal väljer ; detta är ett exempel på ömsesidig rekursion .

    
        
     funktion  pivot(lista, vänster, höger)  // för 5 eller färre element får du bara median  om  höger − vänster < 5  returnerar  sedan  partition5(lista, vänster, höger)  // flyttar annars medianerna för femelements undergrupper till det första n /5 positioner  för  i  från  vänster  till  höger  i steg om  5  // få medianpositionen för den i:te femelements undergruppen  underHöger := i + 4  om  underhöger > höger  sedan  underhöger := höger median5 := partition5(lista, i, underHöger) byt lista[median5] och lista[vänster + våning((i − vänster)/5)]  // beräkna medianen för n/5 medianerna-av-five  mid := (höger − vänster) / 10 + vänster + 1  retur  välj(lista, vänster, vänster + våning((höger − vänster) / 5), mitten)

Partitionshjälpfunktioner

Det finns en subrutin som kallas partition som i linjär tid kan gruppera en lista (från index från vänster till höger ) i tre delar, de som är mindre än ett visst element, de som är lika med det och de som är större än elementet ( en tre- sätt partition ). Grupperingen i tre delar säkerställer att medianen av medianer upprätthåller linjär exekveringstid i ett fall med många eller alla sammanfallande element. Här är pseudokod som utför en partition om elementlistan [pivotIndex] :

    
        
    
        
    
    
        
    
        
     funktionspartition  (lista, vänster, höger, pivotIndex, n) pivotValue := list[pivotIndex] swap lista[pivotIndex] och lista[höger] // Flytta pivot till slutet storeIndex := vänster //  Flytta  alla  element mindre än pivoten till vänster om pivoten  för  i  från  vänster  till  höger − 1  gör  om  list[i] < pivotValue,  byt  sedan lista[storeIndex] och list[i] inkrementera storeIndex   // Flytta alla element lika med pivoten höger efter  // de mindre elementen  storeIndexEq = storeIndex  för  i  från  storeIndex  till  höger − 1  gör  om  list[i] = pivotValue, byt   sedan  lista[storeIndexEq] och list[i] inkrementera storeIndexEq swap list[right] och list[storeIndexEq]  // Flytta pivot till sin slutliga plats  // Returplats för pivot med tanke på den önskade platsen n  om  n < storeIndex  sedan  return  storeIndex  // n är i gruppen av mindre element  om  n ≤ storeIndexEq  då  returnerar  n  // n är i gruppen lika med pivotretur  storeIndexEq  //  n är i gruppen av större element

Subrutinen partition5 väljer medianen för en grupp på högst fem element; ett enkelt sätt att implementera detta är sortering av infogning , som visas nedan. Det kan också implementeras som ett beslutsträd .

 funktion  partition5( lista, vänster, höger) i := vänster + 1  medan  i ≤ höger j := i  medan  j > vänster och lista[j−1] > lista[j]  byter  lista[j−1] och lista[ j] j := j − 1 i := i + 2  returvåning  ((vänster + höger) / 2)

Egenskaper för pivot

Av de ${\frac {n}{5}}$ grupperna, hälften av antalet grupper ( ${\frac {1}{2}}\times { \frac {n}{5}}={\frac {n}{10}}$ ) har sin median mindre än pivoten (median för medianer). Dessutom ytterligare hälften av antalet grupper (igen, ${\frac {1}{2}}\times {\frac {n}{5}}={\frac {n }{10}}$ ) har sin median större än pivoten. I var och en av de ${\displaystyle {\frac {n}{10}}}-$ grupperna med median mindre än pivoten, finns det två element som är mindre än deras respektive medianer, som är mindre än pivoten. Således har var och en av de ${\frac {n}{10}}$ grupperna minst 3 element som är mindre än pivoten. På liknande sätt, i var och en av de ${\displaystyle {\frac {n}{10}}}-$ grupperna med median större än pivoten, finns det två element som är större än deras respektive medianer, som är större än pivoten. Således har var och en av de ${\frac {n}{10}}$ grupperna minst 3 element som är större än pivoten. Pivoten är därför mindre än $3\times {\frac {n}{10}}$ element och större än ytterligare $3\times {\frac {n}{ 10}}$ element. Således delar den valda medianen de ordnade elementen någonstans mellan 30%/70% och 70%/30%, vilket säkerställer algoritmens linjära beteende i värsta fall. För att visualisera:

En iteration på en randomiserad uppsättning av 100 element från 0 till 99
	12	15	11	2	9	5	0	7	3	21	44	40	1	18	20	32	19	35	37	39
	13	16	14	8	10	26	6	33	4	27	49	46	52	25	51	34	43	56	72	79
Medianer	17	23	24	28	29	30	31	36	42	47	50	55	58	60	63	65	66	67	81	83
	22	45	38	53	61	41	62	82	54	48	59	57	71	78	64	80	70	76	85	87
	96	95	94	86	89	69	68	97	73	92	74	88	99	84	75	90	77	93	98	91

(röd = "(en av de två möjliga) medianen av median", grå = "tal < röd", vit = "tal > röd")

5-tuplar visas här sorterade efter median för tydlighetens skull. Att sortera tuplarna är inte nödvändigt eftersom vi bara behöver medianen för användning som pivotelement.

Observera att alla element ovanför/vänster om det röda (30 % av de 100 elementen) är mindre, och alla element under/till höger om det röda (ytterligare 30 % av de 100 elementen) är större.

Bevis på O( n ) gångtid

Det medianberäknande rekursiva anropet överstiger inte det värsta linjära beteendet eftersom listan med medianer har storlek ${\displaystyle {\frac {n}{5}}} ,$ medan det andra rekursiva anropet återkommer på högst 70 % av listan. Låt $T(n)$ vara den tid det tar att köra en median-av-median Quickselect-algoritm på en matris med storleken $n$ . Då vet vi att den här tiden är:

T(n)\leq T(n/5)+T(n\cdot 7/10) +c\cdot n,

var

delen $T\left({\frac {n}{5}}\right)$ är till för att hitta den sanna medianen för ${\frac {n}{5} }$ medianer, genom att köra en (oberoende) snabbval på dem (eftersom att hitta medianen bara är ett specialfall av att välja ett k -minst element)
O ${\displaystyle O(n)}-$ termen $c\cdot n$ är för partitioneringsarbetet för att skapa de två sidorna, varav en av våra Quickselect kommer att återkomma (vi besökte varje element en antal gånger för att bilda dem i n/5 grupper och ta varje median i $O(1)$ tid).
delen $T\left({\frac {7n}{10}}\right)$ är för den faktiska Quickselect-rekursionen (i värsta fall, där det k -te elementet är i den större partitionen som kan ha storleken ${\frac {7n}{10}}$ maximalt)

Genom induktion:

T(n)\leq 10\cdot c\cdot n\in O(n).

Analys

Nyckelsteget är att minska problemet till att välja i två listor vars totala längd är kortare än den ursprungliga listan, plus en linjär faktor för reduktionssteget. Detta möjliggör en enkel induktion för att visa att den totala körtiden är linjär.

Det specifika valet av grupper om fem element förklaras enligt följande. För det första är beräkningsmedianen för en udda lista snabbare och enklare; medan man kan använda en jämn lista, kräver detta att man tar medelvärdet av de två mittelementen, vilket är långsammare än att bara välja det enstaka exakta mittelementet. För det andra är fem det minsta udda talet så att medianen av medianerna fungerar. Med grupper av endast tre element är den resulterande listan med medianer att söka i längden ${\frac {n}{3}}$ och reducerar listan till att återgå till längden ${\ frac {2}{3}}n$ eftersom det är större än 1/2 × 2/3 = 1/3 av elementen och mindre än 1/2 × 2/3 = 1/3 av elementen. Detta lämnar alltså fortfarande $n$ element att söka i, vilket inte minskar problemet tillräckligt. De enskilda listorna är dock kortare och man kan binda den resulterande komplexiteten till $O(n\log n)$ med Akra–Bazzi-metoden , men det bevisar inte linearitet.

Omvänt kan man istället gruppera efter $g$ = sju, nio eller fler element, och det fungerar. Detta minskar storleken på listan med medianer till ${\frac {n}{g}}$ och storleken på listan för att återgå till asymptoter vid 3 n /4 (75%) , som kvadranter i tabellen ovan ungefär 25 %, eftersom storleken på de överlappande linjerna minskar proportionellt. Detta minskar skalfaktorn från 10 asymptotiskt till 4, men höjer följaktligen $c$ för partitioneringsarbetet. Att hitta medianen för en större grupp tar längre tid, men är en konstant faktor (beroende bara på $g$ ), och ändrar alltså inte den totala prestandan när n växer. Med tanke på antalet jämförelser i värsta fall är den konstanta faktorn ${\frac {2g(g-1)}{g-3}}$ .

Om man istället grupperar åt andra hållet, säg att dela elementlistan $n$ i 5 listor, beräkna medianen för var och en och sedan beräkna medianen för dessa – dvs gruppera med en konstant bråkdel, inte ett konstant tal – man minskar inte problemet lika tydligt, eftersom det kräver att man beräknar 5 medianer, var och en i en lista med ${\frac {n}{5}}$ element, och sedan återkommande på en lista med högst ${\frac {7}{10}}n$ . Precis som med gruppering efter 3 är de individuella listorna kortare, men den totala längden är inte kortare – faktiskt längre – och man kan alltså bara bevisa superlinjära gränser. Att gruppera i en kvadrat med ${\sqrt {n}}$ listor med längden ${\sqrt {n}}$ är lika komplicerat.

Blum, M .; Floyd, RW ; Pratt, VR ; Rivest, RL ; Tarjan, RE (augusti 1973). "Tidsgränser för urval" (PDF) . Tidskrift för data- och systemvetenskap . 7 (4): 448–461. doi : 10.1016/S0022-0000(73)80033-9 .

externa länkar

" Lecture notes for January 30, 1996: Deterministic selection ", ICS 161: Design and Analysis of Algorithms, David Eppstein