Konstant (O(1))

Kort sammanfattning: En konstant mängd arbete eller minne behövs oavsett hur stor indatan blir.

Gå direkt till: Tidskomplexitet · Minneskomplexitet · Övning

Förstå tillväxten

Att läsa en bestämd position i en array kräver en indexerad åtkomst oavsett om arrayen har tio eller tio miljoner element. Man behöver inte besöka tidigare element.

När n fördubblas ökar inte antalet primitiva operationer i exemplet. Om en arrayåtkomst räknas som en operation gäller T(n) = c för en fast positiv konstant c.

Vad betyder en konstant övre gräns?

O(1) beskriver en bestämd operation under en bestämd kostnadsmodell. För en array kan adressen till element i beräknas från startadressen, indexet och elementstorleken. Programmet behöver inte läsa elementen som ligger före i. Därför kostar en giltig indexläsning lika många modellsteg oavsett om arrayen innehåller tio eller tio miljoner element.

Det gäller däremot inte arbetet med att hitta rätt index. Om du först måste söka efter ett värde i en osorterad array kan sökningen ta O(n). Den efterföljande läsningen är fortfarande O(1), men hela operationen är O(n). På samma sätt kan det gå snabbt att läsa antalet element i en samling medan det har kostat linjär tid att bygga samlingen.

I en vanlig algoritmanalys räknas aritmetik med heltal av fast bredd som konstanta operationer. Väldigt stora heltal kan kräva längre beräkningar, och cachemissar kan påverka faktisk tid. Big O lovar alltså inte identiska millisekunder, utan att antalet modellerade steg inte växer med n.

Ett genomräknat exempel

För n = 8, n = 8 192 och n = 8 192 000 kräver values[0] fortfarande en uppslagning. Det innebär inte att uppmätt svarstid blir exakt densamma: cache och hårdvara kan påverka resultatet.

Jämför direktläsning med sökning

Tänk dig arrayer med 8, 8 192 respektive 8 192 000 heltal. Uttrycket values[0] utför en indexläsning i samtliga fall. Om uppgiften i stället är att hitta första förekomsten av talet 7 kan en misslyckad linjär sökning behöva läsa varje element: 8, 8 192 respektive 8 192 000 jämförelser.

En hash-tabell ger ofta förväntad O(1)-tid vid uppslagning, men det bygger på antaganden om hashfunktion, beläggning och kollisioner. Den garantin är inte densamma som för en direkt indexläsning i en array. Att byta två redan lagrade, fast stora skalärvärden är ett annat exempel på konstant arbete.

Tidskomplexitet

Exempel för tidsanalys: Läsning av ett känt arrayindex.

Den indexerade åtkomsten förutsätter en riktig array, ett giltigt index och en läsning med konstant kostnad. Gränskontrollen kostar också konstant arbete. Om indexet först måste hittas med en sökning gäller inte längre O(1) för hela operationen. Uppslagning i en hashtabell är ofta förväntat konstant i genomsnitt, men kollisioner kan försämra värsta fallet.

Räkna arbetet för hela operationen

Vid en giltig arrayläsning utförs i en enkel modell en gränskontroll och en minnesläsning. Ingen loop behöver gå igenom arrayen. Men om samma syntax används på en annan datastruktur kan kostnaden skilja sig: för en länkad lista kräver åtkomst till position i normalt att i länkar följs.

Även ett API-anrop som ser ut att läsa en enda post kan kräva indexsökning, kommunikation eller skanning i bakgrunden. Kontrollera därför alltid datastrukturens egenskaper och om operationen inkluderar initiering, sökning eller kopiering. En liten fast loop med tio iterationer är O(1); en loop med n/10 iterationer är fortfarande O(n).

C#

C# | Constant.cs

int first = values[0]; // assuming values is nonempty

C++

C++ | constant.cpp

#include <vector>

int first = values.at(0); // std::vector<int> values; requires nonempty input

Analys: Direkt indexering i en array kräver konstant tid i värsta fall för själva uppslagningen.

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

Minneskomplexitet

Exempel för minnesanalys: Några få lokala heltal.

En summering kan läsa alla element och ändå bara spara en ackumulator och en loopvariabel. Antalet indatavärden växer, men inte antalet lokala variabler. Algoritmen kan därför ha O(n) tid och O(1) extra minne. Indataarrayen tar däremot O(n) plats om den räknas med i totalt minne.

Konstant arbetsminne kan kombineras med linjär tid

Summan i exemplet behåller bara en ackumulator och det aktuella värdet. Antalet extra variabler beror inte på indatans längd: Θ(1) extra minne. Samtidigt måste loopen läsa alla n värden, vilket ger Θ(n) tid. Därför går det inte att dra slutsatser om minneskomplexitet från tidskomplexitet.

Om själva indataarrayen räknas med upptar den Θ(n) totalt minne. En ny kopia skulle dessutom kräva Θ(n) extra minne. En rekursiv genomgång som behåller ett anrop per element kan behöva Θ(n) stackutrymme trots att varje anrop bara lagrar ett enda index. Det avgörande är hur många värden som finns samtidigt.

C#

C# | Constant.cs

int total = 0;
foreach (int value in values) total += value;

C++

C++ | constant.cpp

int sum = 0;
for (int value : values) sum += value; // constant extra storage

Analys: En ackumulator använder O(1) extra minne även om loopen tar O(n) tid.

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

Så känner du igen O(1)

Typiska exempel är en giltig arrayindexering, läsning av en lagrad längd, ökning av en räknare av fast storlek och byte mellan två skalärvärden. Men det är enskilda operationer, inte ett löfte om hela algoritmen. Hashuppslagning har ofta god förväntad kostnad men kan få sämre värsta fall när många nycklar kolliderar.

Skilj också på konstant extra minne och konstant totalt minne. En funktion som tar emot en stor array och använder två räknare har konstant extra minne, även om arrayen själv är stor. Beskriv vilken resurs och vilken del av programmet gränsen gäller.

Praktiskt exempel: inventarieplatser i ett spel

En array med inventarieplatser kan läsa plats 12 direkt, förutsatt att indexet är giltigt. En större inventarie gör inte att just den läsningen måste gå igenom tidigare platser. En knapp för att hitta första lediga platsen kan däremot behöva skanna alla platser och får O(n) tid i värsta fall. En dictionary från föremåls-ID till plats kan göra förväntade uppslagningar snabbare men kräver extra minne och hantering av kollisioner.

Metodnamnet GetItem säger inget säkert om komplexiteten. Ta reda på om argumentet är ett index, ett föremåls-ID eller ett villkor som kräver sökning. Kontrollera också om metoden bygger en lista innan den returnerar ett enda värde. Även förarbetet måste räknas.

Vanligt misstag

Se upp: Kalla inte en hel algoritm O(1) bara för att en enskild sats har konstant kostnad. Att skapa en array med n element, kopiera värden eller först söka efter ett index förändrar helhetens kostnad.

Testa kunskaperna

Implementera en summering av en array och klassificera tid respektive extra minne var för sig. Förklara varför svaren skiljer sig.

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