Linjärlogaritmisk (O(n log n))

Kort sammanfattning: Ungefär logaritmiskt många nivåer bearbetar tillsammans n element per nivå.

Gå direkt till: Tidskomplexitet · Minneskomplexitet · Övning

Förstå tillväxten

Tänk dig att en array delas i halvor gång på gång och sedan byggs ihop av sorterade delar. Under varje sammanslagningsnivå behandlas varje element ett begränsat antal gånger. Antalet nivåer växer med log₂(n).

För n = 8 har en balanserad uppdelning ungefär tre nivåer, för n = 16 ungefär fyra. På varje nivå kräver mergesort sammanlagt O(n) arbete. Multiplikationen ger T(n) = O(n log n), inte O(log n) bara för att indatan halveras.

Här kommer faktorerna n och log n ifrån

Merge sort delar sekvensen i två halvor och slår därefter ihop sorterade delsekvenser. Antalet nivåer är ungefär log₂(n). På varje nivå passerar de olika sammanslagningarna tillsammans alla n elementen. Det blir Θ(n) arbete per nivå och Θ(log n) nivåer, alltså Θ(n log n) totalt.

En vanlig rekursionsekvation är T(n) = 2T(n/2) + Θ(n). De två första termerna motsvarar sorteringen av respektive halva och den sista sammanslagningen. Att enbart titta på halveringen ger fel slutsats O(log n), eftersom varje nivå fortfarande behandlar många element.

För jämförelsebaserad sortering av godtyckliga unika element finns också en allmän Ω(n log n)-gräns i värsta fall. Sorteringsmetoder som utnyttjar begränsade nyckelvärden kan ha andra gränser. En biblioteksmetod är inte automatiskt merge sort; kontrollera implementationens dokumenterade garantier.

Ett genomräknat exempel

För n = 1 024 är log₂(n) = 10, så tio hela genomgångar motsvarar ungefär 10 240 elementbehandlingar. För n = 2 048 ger elva nivåer ungefär 22 528. Dubbelt så stor indata ger lite mer än dubbelt så mycket arbete.

Räkna nivå för nivå

För åtta element finns tre sammanfogningsnivåer. Först slås fyra par ihop, sedan två grupper och till sist två halvor. På varje nivå bearbetas totalt åtta element, alltså omkring 8 × 3 = 24 enheter i en pedagogisk arbetsmodell. Det är inte ett exakt antal jämförelser.

För 16 element finns fyra nivåer och ungefär 64 sådana arbetsenheter. För 1 024 element finns tio nivåer och cirka 10 240. Indatan fördubblas och arbetet ökar lite mer än dubbelt, men långt mindre än vid kvadratisk tillväxt.

Tidskomplexitet

Exempel för tidsanalys: Mergesort och delningsnivåer.

Mergesort ger O(n log n) i värsta fall när sammanslagningen är linjär och delningen balanserad. Generell jämförelsesortering har en undre gräns Ω(n log n) i värsta fall för godtyckliga distinkta värden, men specialiserad sortering kan följa andra regler. Kodexemplet nedan utför faktiskt delningen och sammanslagningen. Tidsgränsen härleds från dessa steg, inte från namnet på ett biblioteksanrop.

Räkna sammanslagningarna

Vid sammanslagningen flyttas pekarna genom två sorterade delsekvenser. Varje element matas in i resultatet en gång, så en sammanslagning av totalt m element kräver Θ(m) arbete. Summeringen över samtliga sammanslagningar på en nivå blir Θ(n). Med Θ(log n) nivåer ger det Θ(n log n).

Analysen förutsätter jämförelser och elementflyttar med konstant modellkostnad. Långa strängjämförelser eller onödiga kopior kan förändra den verkliga kostnaden. Det är den konkreta algoritmen som ger garantin, inte enbart namnet på ett sorteringsanrop.

C#

C# | Linearithmic.cs

static void MergeSort(int[] values)
{
  int[] temp = new int[values.Length];
  SortRange(values, temp, 0, values.Length);
}

static void SortRange(int[] a, int[] temp, int start, int end)
{
  if (end - start <= 1) return;
  int mid = start + (end - start) / 2;
  SortRange(a, temp, start, mid);
  SortRange(a, temp, mid, end);

  int left = start, right = mid;
  for (int k = start; k < end; k++)
  {
      if (left < mid && (right == end || a[left] <= a[right]))
          temp[k] = a[left++];
      else
          temp[k] = a[right++];
  }
  Array.Copy(temp, start, a, start, end - start);
}

C++

C++ | linearithmic.cpp

#include <algorithm>
#include <vector>

void sortRange(std::vector<int>& a, std::vector<int>& temp,
             int start, int end) {
  if (end - start <= 1) return;
  int mid = start + (end - start) / 2;
  sortRange(a, temp, start, mid);
  sortRange(a, temp, mid, end);

  int left = start, right = mid;
  for (int k = start; k < end; ++k) {
      if (left < mid && (right == end || a[left] <= a[right]))
          temp[k] = a[left++];
      else
          temp[k] = a[right++];
  }
  std::copy(temp.begin() + start, temp.begin() + end,
            a.begin() + start);
}

void mergeSort(std::vector<int>& values) {
  std::vector<int> temp(values.size());
  sortRange(values, temp, 0, static_cast<int>(values.size()));
}

Analys: Varje sammanslagningsnivå bearbetar sammanlagt Θ(n) element. Med Θ(log n) nivåer ger just den här implementationen Θ(n log n) tid i värsta fall och Θ(n) extra buffertminne.

Båda kodexemplen visar en fullständig top-down-merge-sort med en återanvänd buffert. Sammanslagningen använder <= för att bevara ordningen mellan lika värden. Antagandet är att jämförelser och elementflyttar har konstant kostnad.

Minneskomplexitet

Exempel för minnesanalys: En tabell med n gånger log n celler.

En tabell med n rader och ungefär log₂(n) kolumner lagrar O(n log n) celler. Det är klassens minnesexempel, inte normal minnesanalys för mergesort. En vanlig arraybaserad mergesort använder ofta O(n) buffert och O(log n) stackramar. Dess tid och minne tillhör därför olika klasser. En tabell som sparar alla nivåer är en annan struktur.

Merge sort använder normalt inte n log n extra minne

En vanlig merge-sort-implementation använder en tillfällig array för upp till n element. Den ger Θ(n) extra minne, medan rekursionsstacken bidrar Θ(log n). Tillsammans dominerar den linjära bufferten. Ofta kan samma buffert återanvändas genom hela sorteringen.

Det separata tabell-exemplet lagrar däremot n rader och omkring log n kolumner samtidigt. Det illustrerar Θ(n log n) minne, men är inte ett krav för vanlig merge sort. Om flera buffertar skapas i rekursionen måste man undersöka hur länge de är aktiva innan deras minne summeras.

C#

C# | Linearithmic.cs

// Assumes n >= 1; check dimensions and allocation limits.
int levels = (int)Math.Log2(n);
int[,] table = new int[n, levels + 1];

C++

C++ | linearithmic.cpp

#include <vector>
#include <cmath>

// Assumes n >= 1 and a representable allocation size.
int levels = static_cast<int>(std::log2(n));
std::vector<std::vector<int>> table(n, std::vector<int>(levels + 1));

Analys: En tabell med n gånger log n celler tar O(n log n) minne; mergesort använder vanligtvis O(n) extra minne, inte O(n log n).

Minnesgränsen avser allokerade element och aktiva anropsramar; faktisk overhead beror på runtime, allocator och elementtyp.

När är linjärlogaritmisk tid användbar?

Merge sort har förutsägbar O(n log n)-tid i värsta fall. Den kan dessutom vara stabil om lika värden hanteras i ursprunglig ordning, vilket är praktiskt vid sortering av poster efter flera nycklar. Den vanliga arrayvarianten använder däremot extra minne.

Även n operationer som var och en kostar Θ(log n), till exempel vissa operationer i balanserade sökträd, ger sammanlagt Θ(n log n). Fråga därför om logaritmen kommer från nivåer i en rekursion eller kostnad per element.

Praktiskt exempel: sortera matchresultat

Efter en multiplayer-match kan topplistan sortera n spelarresultat efter poäng och sedan en sekundär nyckel. En stabil merge sort kan bevara ursprungsordningen för poster med lika sorteringsnyckel, vilket är användbart om sorteringen görs i flera steg. Antalet jämförelser i värsta fall växer som Θ(n log n), men en vanlig implementation behöver också Θ(n) extra buffertminne.

För en mycket liten topplista kan en enklare metod fungera lika bra. Vid stora återkommande sorteringar blir den förutsägbara tillväxten viktigare. Kontrollera alltid vad den aktuella sorteringsfunktionen dokumenterar om stabilitet och komplexitet; metodnamnet Sort är inte en sådan garanti.

Vanligt misstag

Se upp: Antalet rekursionsnivåer är inte samma sak som total körtid. Summera arbetet över alla noder på varje nivå. Skilj även på en tabell som sparar alla nivåer och en temporär buffert som återanvänds.

Testa kunskaperna

Följ mergesort för åtta värden och räkna sammanslagningsarbetet per nivå. Rita sedan högsta samtidiga användning av buffert och stack.

1. Definiera exakt vad n betyder i exemplet.
2. Räkna huvudoperationen i bästa och värsta fall där det är relevant.
3. Räkna största samtidiga minnesmängd.
4. Kontrollera resultatet i Big O-visualiseraren.

Fortsätt läsa

Big O-översikt · Tidskomplexitet · Minneskomplexitet · Jämför klasser