Waarom is merge sort worst case runtime O (n log n)?

Kan iemand het me uitleggen in eenvoudig Engels of op een makkelijke manier om het uit te leggen?

Antwoord 1, autoriteit 100%

Bij een “traditionele” samenvoegsortering verdubbelt elke passage door de gegevens de grootte van de gesorteerde subsecties. Na de eerste doorgang wordt het bestand gesorteerd in secties van lengte twee. Na de tweede pas, lengte vier. Dan acht, zestien, enz. tot de grootte van het bestand.

Het is noodzakelijk om de grootte van de gesorteerde secties steeds te verdubbelen totdat er één sectie is die het hele bestand omvat. Er zijn lg(N) verdubbelingen van de sectiegrootte nodig om de bestandsgrootte te bereiken, en elke passage van de gegevens kost tijd die evenredig is aan het aantal records.

Antwoord 2, autoriteit 93%

De Samenvoegen Sorterengebruiken de Verdeel-en-heers-aanpak om het sorteerprobleem op te lossen. Ten eerste deelt het de invoer in tweeën met behulp van recursie. Na het verdelen sorteert het de helften en voegt het samen tot één gesorteerde uitvoer. Zie de afbeelding

Het betekent dat het beter is om eerst de helft van je probleem te sorteren en een eenvoudige subroutine samen te voegen. Het is dus belangrijk om de complexiteit van de merge-subroutine te kennen en hoe vaak deze in de recursie zal worden aangeroepen.

De pseudo-code voor de samenvoegsorteringis heel eenvoudig.

# C = output [length = N]
# A 1st sorted half [N/2]
# B 2nd sorted half [N/2]
i = j = 1
for k = 1 to n
    if A[i] < B[j]
        C[k] = A[i]
        i++
    else
        C[k] = B[j]
        j++

Het is gemakkelijk om te zien dat in elke lus je 4 operaties hebt: K ++ , I ++ of J ++ , de als Statement en de Attribution C = A | B . U hebt dus minder of gelijk aan 4N + 2-operaties die een o (n) complexiteit geven. Omwille van het bewijs zal 4n + 2 worden behandeld als 6N, aangezien het waar is voor n = 1 (4n +2 & lt; = 6n ).

Dus ga eraan dat je een invoer hebt met N -elementen en veronderstel N is een kracht van 2. Op elk niveau heb je twee keer meer subproblemen met een invoer met halve elementen van de vorige invoer. Dit betekent dat op het niveau J = 0, 1, 2, …, LGN er 2 ^ j subproblemen zijn met een invoer van de lengte n / 2 ^ j . Het aantal bewerkingen op elk niveau J is minder of gelijk aan

2 ^ j * 6 (N / 2 ^ j) = 6n

Houd er rekening mee dat het niet het niveau maakt dat u altijd minder of gelijke 6N-operaties hebt.

Aangezien er LGN + 1-niveaus zijn, is de complexiteit

O (6N * (LGN + 1)) = O (6N * LGN + 6N) = o (n lgn)

Referenties:

• Coursera Course Algoritmen: ontwerp en analyse, deel 1

Antwoord 3, Autoriteit 67%

Na het splitsen van de array op het podium waar u enkele elementen hebt, d.w.z. noem ze sublijsten,

• In elke fase vergelijken we elementen van elke sublist met zijn aangrenzende sublist. Bijvoorbeeld [hergebruik @ davi’s afbeelding
  ]

  

  1. Bij fase-1 wordt elk element vergeleken met zijn aangrenzende, dus N / 2-vergelijkingen.
  2. In Fase-2 wordt elk element van sublist vergeleken met zijn aangrenzende sublijst, omdat elke sublijst is gesorteerd, dit betekent dat het maximale aantal vergelijkingen tussen twee sublijst is gemaakt en lt; = lengte van de sublist IE 2 (in het stadium -2) en 4 vergelijkingen in fase-3 en 8 in fase-4, aangezien de sublisters in lengte verdubbelen. Dat betekent het maximale aantal vergelijkingen in elke fase = (lengte van sublist * (aantal sublijst / 2)) == & GT; n / 2
  3. Zoals u hebt waargenomen, zou het totale aantal fasen log(n) base 2zijn
     Dus de totale complexiteit zou == (maximaal aantal vergelijkingen in elk stadium * aantal fasen) == O ((N / 2) * log (n)) == & GT; O (NLOG (N))

Antwoord 4, Autoriteit 59%

Dit komt omdat het het ergste geval is of gemiddeld geval de samenvoeging sorteert de array in twee helften in elke fase die het LG (N) -component geeft en de andere n-component komt van zijn vergelijkingen die in elke fase zijn gemaakt . Dus het combineren wordt bijna o (nlg n). Het maakt niet uit of is gemiddelde zaak of het ergste geval, LG (N) factor is altijd aanwezig. Rust n Factor hangt af van de gemaakt vergelijkingen die uit de vergelijkingen in beide gevallen worden gedaan. Nu is het ergste geval één waarin n-vergelijkingen gebeurt voor een N-invoer in elke fase. Dus het wordt een O (NLG N).

Antwoord 5, Autoriteit 49%

Algoritme samenvoegen-sorteren Sorteert een sequentie S van Size N in O (n log n)
Tijd, uitgaande dat twee elementen van S kunnen worden vergeleken in O (1) tijd.

Antwoord 6, Autoriteit 18%

Veel van de andere antwoorden zijn geweldig, maar ik heb geen vermelding gezien van hoogte en diepte gerelateerd aan voorbeelden “samenvoegen-sorteboom”. Hier is een andere manier om de vraag te benaderen met veel focus op de boom. Hier is een ander beeld om te helpen verklaren:

Gewoon een recap: zoals andere antwoorden hebben gewezen, weten we dat het werk van het samenvoegen van twee gesorteerde plakjes van de reeks in lineaire tijd (de samenvoeghelperfunctie die we van de hoofdsorterende functie noemen).
Nu kijkend naar deze boom, waar we kunnen denken aan elke afstammeling van de wortel (anders dan de root) als een recursieve oproep naar de sorteerfunctie, laten we proberen te beoordelen hoeveel tijd we aan elk knooppunt doorbrengen … sinds het snijden van De volgorde en het samenvoegen (beide samen) nemen lineaire tijd, de looptijd van een knooppunt is lineair met betrekking tot de lengte van de reeks in dat knooppunt.

Hier is waar boomdiepte binnenkomt. Als n de totale grootte van de oorspronkelijke volgorde is, is de grootte van de sequentie op elk knooppunt N / 2 ^{I , waar ik de diepte is. Dit wordt weergegeven in de afbeelding hierboven. Dit samen met de lineaire hoeveelheid werk voor elke plak plaatsen, hebben we een looptijd van O (N / 2 I ) voor elk knooppunt in de boom. Nu moeten we gewoon zo goed voor de n-knooppunten. Een manier om dit te doen, is het erkennen dat er 2 i knooppunten op elk niveau van diepte in de boom zijn. Dus voor elk niveau hebben we O (2 I * N / 2 I ), die O (n) is omdat we de 2 I s! Als elke diepte O (n) is, moeten we het gewoon vermenigvuldigen door de -hoogte van deze binaire boom, die logn is. Antwoord: O (nlogn)}

referentie: Datastructuren en algoritmen in Python

Antwoord 7, autoriteit 10%

MergeSort-algoritme in drie stappen:

1. Deelstap berekent middenpositie van sub-array en het kost constante tijd O(1).
2. Veroverenstap recursief sorteren van twee subarrays van elk ongeveer n/2 elementen.
3. Combineerstap voegt een totaal van n elementen samen bij elke passage waarvoor maximaal n vergelijkingen nodig zijn, dus er is O(n) nodig.

Het algoritme vereist ongeveer logn-passages om een array van n elementen te sorteren en dus is de totale tijdcomplexiteit nlogn.

Antwoord 8, autoriteit 10%

De recursieve boom heeft diepte log(N), en op elk niveau in die boom doe je een gecombineerd N-werk om twee gesorteerde arrays samen te voegen.

Gesorteerde arrays samenvoegen

Om twee gesorteerde arrays A[1,5]en B[3,4]samen te voegen, herhaalt u beide, beginnend bij het begin, en kiest u het laagste element tussen de twee arrays en het verhogen van de aanwijzer voor die array. U bent klaar wanneer beide aanwijzers het einde van hun respectieve arrays bereiken.

[1,5] [3,4]  --> []
 ^     ^
[1,5] [3,4]  --> [1]
   ^   ^
[1,5] [3,4]  --> [1,3]
   ^     ^
[1,5] [3,4]  --> [1,3,4]
   ^      x
[1,5] [3,4]  --> [1,3,4,5]
    x     x
Runtime = O(A + B)

Samenvoegen van sorteerillustratie

Uw recursieve call-stack ziet er als volgt uit. Het werk begint bij de onderste bladknopen en borrelt omhoog.

beginning with [1,5,3,4], N = 4, depth k = log(4) = 2
  [1,5]    [3,4]     depth = k-1 (2^1 nodes) * (N/2^1 values to merge per node) == N
[1]  [5]  [3]  [4]   depth = k   (2^2 nodes) * (N/2^2 values to merge per node) == N

Dus u doet NWERKEN IN ELK kNIVEADEN IN DE BOOM, waarbij k = log(N)

N * k = N * log(N)