Logaritmisk (O(log n))

Kort sammanfattning: Varje steg tar bort en bestämd andel av de återstående möjligheterna, vilket ger ett logaritmiskt antal steg.

Gå direkt till: Tidskomplexitet · Minneskomplexitet · Övning

Förstå tillväxten

Tänk dig att slå upp ett ord i en sorterad ordbok genom att börja nära mitten och sedan välja rätt halva. Varje beslut tar bort ungefär hälften av kandidaterna. Binärsökning använder samma idé på sorterade data med snabb indexåtkomst.

Efter k halveringar finns högst ungefär n / 2^k kandidater kvar. Villkoret n / 2^k <= 1 ger k >= log₂(n). Att byta logaritmens bas förändrar bara resultatet med en konstant faktor och därmed inte Big O-klassen.

Varför halvering leder till logaritmer

Binärsökning upprätthåller ett intervall som fortfarande kan innehålla målvärdet. Efter jämförelsen med mittvärdet kan hela den ena halvan kastas bort. Efter k steg återstår ungefär n / 2^k kandidater. När det bara finns en kandidat kvar är k ungefär log₂(n). En fördubbling av indatan ger därmed bara omkring ett extra halveringssteg.

Faktorn måste inte vara två. Om mängden minskar till en tredjedel varje gång får vi log₃(n) steg, vilket ändå är O(log n). Det är den multiplikativa minskningen som kännetecknar tillväxten, inte att ett divisionsuttryck råkar förekomma i koden.

Binärsökning förutsätter sorterade data och effektiv åtkomst till mitten. En sorterad array fungerar väl, men en länkad lista kan kräva lång genomgång för att komma till mitten. Om indatan inte är sorterad är själva beslutet om vilken halva som ska kastas bort felaktigt.

Ett genomräknat exempel

För 1 024 kandidater ger tio halveringar ett kvarvarande element. För 2 048 kandidater behövs elva. Indatan fördubblas men antalet halveringar ökar bara med ett. Det faktiska antalet jämförelser påverkas även av implementationens avslutningsvillkor.

Följ ett konkret sökintervall

Sök efter 23 i [3, 7, 12, 18, 23, 29, 34, 41]. Första mittvärdet är 18 vid index 3. Då kan index 0 till 3 kastas bort. I det återstående intervallet väljer koden index 5, värdet 29, och behåller den vänstra delen. Den tredje jämförelsen träffar 23 vid index 4.

Om målet i stället är 20 krymper intervallet tills lo > hi och funktionen returnerar -1. En variant som söker insättningsposition (lower bound) ger ett index i stället. Båda kan vara logaritmiska men har olika kontrakt, särskilt vid dubbletter.

Tidskomplexitet

Exempel för tidsanalys: Binärsökning i sorterade data.

Vanlig iterativ binärsökning undersöker mittvärdet och behåller bara ena halvan. I värsta fall fortsätter den tills intervallet är tomt, vilket ger O(log n) jämförelser. Om första mittvärdet matchar blir bästa fallet O(1). Indatan måste vara sorterad och ha effektiv indexåtkomst. Att gå till mitten av en länkad lista kostar något annat. Webbplatsens tidigare kod visade en lower-bound-variant som returnerar insättningsposition, inte -1 om målet saknas.

Bevisa att intervallet verkligen minskar

Efter varje misslyckad jämförelse ändras antingen lo till mid + 1 eller hi till mid - 1. Mittpunkten försvinner alltså alltid ur intervallet; annars kan loopen fastna. Uttrycket lo + (hi - lo) / 2 undviker dessutom ett potentiellt overflowproblem med lo + hi i vissa heltalsrepresentationer.

Bästa fallet är Θ(1) när första mittvärdet matchar. Värsta fallet är Θ(log n), eftersom varje steg behåller högst ungefär hälften av kandidaterna. Ett genomsnittsfall kräver antaganden om vilka värden som söks. Jämförelser och indexläsningar antas ha konstant kostnad för element av fast storlek.

C#

C# | Logarithmic.cs

static int BinarySearch(int[] values, int target)
{
    int lo = 0, hi = values.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

C++

C++ | logarithmic.cpp

#include <vector>

int binarySearch(const std::vector<int>& values, int target) {
    int lo = 0, hi = static_cast<int>(values.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Analys: Iterativ binärsökning kräver sorterad array och har O(log n) tid i värsta fall.

C++-exemplet visar samma grundidé, men kompilator, container och anropade funktioner måste ingå i en fullständig komplexitetsanalys.

Minneskomplexitet

Exempel för minnesanalys: Rekursivt halveringsdjup.

En rekursiv halveringsfunktion kan skapa en aktiv anropsram för varje nivå. Bara en rekursiv gren är aktiv åt gången, men alla väntande anrop finns kvar på stacken. Djupet är Θ(log n), vilket ger O(log n) stackminne. Iterativ binärsökning lagrar i stället några få index och använder O(1) extra minne. Inget av dessa mått beskriver storleken på själva indataarrayen.

Iterativ och rekursiv lösning använder olika minne

Iterativ binärsökning lagrar ett fåtal index: lo, hi och mid. Därför behövs Θ(1) extra minne även för en stor array. Det separata rekursionsexemplet Visit(n / 2) behåller däremot en aktiv anropsram per halvering. Vid n = 1 024 kan ungefär elva ramar vara aktiva inklusive basfallet, vilket ger Θ(log n) stackdjup.

Det görs bara ett rekursivt underanrop i minnesexemplet. En annan rekursion kan utföra två underanrop och ändå ha logaritmiskt stackdjup om de behandlas efter varandra, men dess totala tidsarbete kan vara större. Om varje anrop dessutom behåller en växande buffert måste minnesanalysen ta hänsyn till buffertarnas storlek och livslängd.

C#

C# | Logarithmic.cs

void Visit(int n)
{
    if (n <= 1) return;
    Visit(n / 2);
}

C++

C++ | logarithmic.cpp

void visit(int n) {
    if (n <= 1) return;
    visit(n / 2); // one live call per halving
}

Analys: Det rekursiva exemplet har O(log n) stackdjup; iterativ binärsökning har O(1) extra minne.

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

När passar logaritmisk sökning?

Metoden passar när kandidaterna är ordnade och en kontroll vid mittpunkten pålitligt avgör vilken sida som kan ignoreras. Det gäller både exakt sökning, första värdet som är minst x och sökning efter en gräns där ett monotont villkor växlar värde. Balanserade sökträd kan också ge logaritmiska sökvägar, men då beror garantin på balansreglerna.

En rekursiv funktion är inte automatiskt logaritmisk: att minska n med ett ger linjärt djup. Att halvera problemet och samtidigt skanna alla n värden på varje nivå kan ge Θ(n log n) tid. Räkna både antal nivåer och arbete per nivå.

Praktiskt exempel: sökning efter en poänggräns

Tänk dig sorterade spelarpoäng där topplistan ska hitta första poängen som är minst 1 000. En lower-bound-binärsökning passar bra: efter varje jämförelse kastas den halva bort som inte kan innehålla den första godkända poängen. Även om flera spelare har samma poäng förblir sökningen O(log n), om gränserna flyttas korrekt.

Om användaren däremot vill se alla spelare över gränsen kan många resultat behöva skrivas ut. Att hitta första indexet kostar O(log n), men att presentera k resultat lägger till O(k). Hela åtgärden blir därför O(log n + k), trots den snabba inledande sökningen.

Vanligt misstag

Se upp: En halverande rekursion har inte automatiskt O(log n) tid. Om varje nivå bearbetar n värden kan arbetet bli O(n log n). Räkna arbetet inne i anropen.

Testa kunskaperna

Förutsäg antal halveringar för 64, 1 024 och 65 536 kandidater. Jämför sedan extra minne vid iterativ binärsökning med rekursivt stackdjup.

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