Linjär (O(n))

Kort sammanfattning: Arbetet eller extraminnet växer i direkt proportion till antalet element.

Gå direkt till: Tidskomplexitet · Minneskomplexitet · Övning

Förstå tillväxten

Föreställ dig att kontrollera varje vara på en hylla tills du hittar rätt etikett. Utan index eller genväg kan dubbelt så många varor innebära dubbelt så många jämförelser i värsta fall.

En loop som utför en operation med konstant kostnad för vart och ett av n element har T(n) = a·n + b för konstanter a och b. Big O bortser från dessa faktorer och ger O(n). Det betyder inte att varje körning besöker alla element.

Varför en komplett genomgång är linjär

För att avgöra om ett värde saknas i en osorterad array utan extra indexering måste sökningen kontrollera varje element. Ett värde kan ligga sist, och då utförs n jämförelser. Värsta fallet för enkel linjär sökning är därför Θ(n), även om en lyckad sökning ibland kan avslutas efter bara ett steg.

Samma tillväxt uppstår när du räknar positiva tal, hittar största värdet eller skapar en ny representation med ett resultat per indataelement. Två kompletta genomgångar ger ungefär 2n operationer och fortfarande Θ(n). Men om varje element är en lång sträng kan jämförelsen kosta mer än ett steg; då kan den sammanlagda stränglängden vara ett bättre mått än bara antalet objekt.

Linjär tid är inte automatiskt dålig. Om varje element verkligen måste bidra till svaret kan Θ(n) vara optimalt. Att skapa ett index kan snabba upp framtida sökningar, men indexet tar tid och minne att bygga.

Ett genomräknat exempel

En fullständig genomgång av 50 element gör högst 50 kontroller, medan 100 element ger högst 100. En kopia av 100 heltal innehåller ungefär dubbelt så många kopierade värdebytes som en kopia av 50.

Följ målpositionen

Sök efter 8 i [8, 4, 6, 2, 1]: en jämförelse räcker. Sök efter 1: fem jämförelser behövs. Sök efter 99: alla fem element kontrolleras innan -1 returneras. Om arrayen i stället innehåller 50 värden kräver en misslyckad sökning 50 jämförelser.

Om målet med säkerhet förekommer exakt en gång och alla positioner är lika sannolika blir det förväntade antalet jämförelser (n+1)/2. Det är fortfarande Θ(n), men beräkningen förutsätter en viss fördelning. Den gäller inte automatiskt för alla sökmönster.

Tidskomplexitet

Exempel för tidsanalys: Genomgång av varje element.

Linjär sökning jämför varje arrayelement med målet och returnerar index för den första träffen. Om målet ligger först är bästa fallet O(1). Om det ligger sist eller saknas läses alla n element, vilket ger O(n) i värsta fall. Påståenden om genomsnitt kräver antaganden om målets placering. Binärsökning kan inte användas direkt på osorterade data.

Tidigt avslut och dolt extraarbete

Loopen kontrollerar indexen i stigande ordning och återbesöker inget index. Därför gör den högst n jämförelser. Bästa fallet är Θ(1), värsta fallet Θ(n). Om du stoppar in en ny fullständig sökning i loopkroppen kan kostnaden däremot öka till Θ(n²).

Att stega med två index i taget ger ungefär n/2 iterationer och är fortfarande linjärt. En loop som halverar det återstående intervallet ger däremot logaritmiskt antal iterationer. Undersök hur antalet återstående objekt förändras i varje steg.

C#

C# | Linear.cs

int Find(int[] values, int target)
{
    for (int i = 0; i < values.Length; i++)
        if (values[i] == target) return i;
    return -1;
}

C++

C++ | linear.cpp

#include <vector>

int findIndex(const std::vector<int>& values, int target) {
    for (std::size_t i = 0; i < values.size(); ++i)
        if (values[i] == target) return static_cast<int>(i);
    return -1;
}

Analys: Linjär sökning har O(n) i värsta fall och O(1) i bästa fall när första elementet matchar.

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

Minneskomplexitet

Exempel för minnesanalys: Kopiering av en array.

När en array kopieras skapas en andra array med n element, vilket kräver O(n) extra minne medan originalet finns kvar. Kopieringen tar också O(n) tid. En sökning som bara lagrar index och målvärde använder däremot O(1) extra minne. Båda kan ta linjär tid men har olika minnesåtgång. Ange om en skapad utdataarray räknas som extra minne.

Kopiering och strömmande beräkning

En kopia av n heltal skapar en ny array med n element som finns kvar efter kopieringen: Θ(n) extra minne om utdata räknas med. Kopieringen kräver också Θ(n) tid eftersom varje element måste läsas och skrivas.

En summa som beräknas i ett enda genomlopp kan däremot använda Θ(1) extra minne. En rekursiv genomgång av n noder kan behålla Θ(n) stackramar, medan en iterativ lösning vanligtvis behöver bara en aktuell pekare. Att samma uppgift kan lösas med olika minneskostnad gör resursmåttet särskilt viktigt.

C#

C# | Linear.cs

int[] copy = new int[values.Length];
Array.Copy(values, copy, values.Length);

C++

C++ | linear.cpp

#include <vector>

std::vector<int> copy = values; // O(n) copied element storage

Analys: Arraykopian använder O(n) extra minne och tar samtidigt O(n) tid.

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

När är en linjär lösning rätt val?

För korta listor eller enstaka sökningar är en enkel skanning ofta smidig. Den behöver ingen förberedelse och fungerar väl med sekventiell lagring. Om många sökningar ska utföras i samma data kan ett hashindex eller en sorterad struktur löna sig, men byggkostnaden måste räknas in.

Om du ska producera n utdataelement krävs minst Ω(n) arbete enbart för att skriva dem. Jämför därför hela uppgiften: förberedelse, varje fråga och hur mycket minne lösningen behöver, inte bara ett enskilt API-anrop.

Praktiskt exempel: granska spelarpoäng

En server som vill hitta högsta poängen bland anslutna spelare måste i värsta fall granska alla om den inte redan underhåller ett index eller en sammanfattning. En osedd spelare kan annars ha högst värde. Genomgången tar Θ(n) tid men behöver bara Θ(1) extra minne för bästa poäng och en spelarreferens. Om servern också bygger en sorterad topplista är det en separat operation som måste analyseras för sig.

Strömmande data och sekventiell filbehandling passar ofta för sådana förutsägbara genomgångar. Ett index kan löna sig när samma data ska sökas många gånger, men det tillför bygg- och underhållskostnader.

Vanligt misstag

Se upp: En enda loop är inte automatiskt O(n): arbetet inne i loopen spelar roll. Om varje iteration gör en ny sökning eller jämför långa strängar kan hela kostnaden bli större.

Testa kunskaperna

Skriv två sökningar: en som avslutas vid första träffen och en som räknar alla träffar. Jämför bästa och värsta fall.

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