Kvadratrot (O(√n))

Kort sammanfattning: Antalet operationer eller minnesceller växer med kvadratroten ur ett numeriskt värde n.

Gå direkt till: Tidskomplexitet · Minneskomplexitet · Övning

Förstå tillväxten

Om ett positivt heltal har en äkta delare måste minst en av faktorerna vara högst kvadratroten ur talet. Därför räcker det att testa kandidater upp till denna gräns vid enkel primtalstestning.

Om det numeriska värdet fyrdubblas fördubblas kvadratroten: √(4n) = 2√n. Detta växer långsammare än n, men snabbare än log n. Här är n heltalets värde, inte antalet bitar som behövs för att lagra det.

Varför räcker det att prova upp till kvadratroten?

Ett sammansatt heltal kan skrivas som a × b. Om båda faktorerna vore större än √n skulle produkten bli större än n. Därför måste minst en faktor vara högst √n. Vid enkel primtalstestning räcker det att leta efter delare upp till denna gräns, vilket ger O(√n) kandidatprov i en modell där aritmetik på heltal av fast storlek kostar konstant tid.

Här betyder n heltalets numeriska värde, inte längden i bitar. Ett positivt heltal med b bitar kan ha ett värde nära 2^b. Då är ett antal steg som växer med √n inte samma sak som O(√b). Skillnaden är viktig vid teoretisk analys av algoritmer för mycket stora heltal.

Kvadratrotsklassen kan också uppstå vid blockindelning av arrayer: dela n element i block av ungefär storleken √n och lagra en sammanfattning per block. Hur snabbt uppslagningar och uppdateringar går beror på vilka sammanfattningar som används.

Ett genomräknat exempel

För värdet 100 är kvadratroten 10, för 10 000 är den 100 och för 1 000 000 är den 1 000. När talets värde blir hundra gånger större växer antalet kandidatdelare ungefär tio gånger.

Testa två olika tal

För n = 97 prövar koden delarna 2 till 9 och hittar ingen faktor. Den gör åtta restberäkningar innan den kan svara att talet är primtal. För n = 100 hittar den däremot delaren 2 direkt och avslutar tidigt. Det är därför tal utan små faktorer som styr värsta fallet.

Vid 10 000 är kvadratrotsgränsen 100, och vid 1 000 000 är den 1 000. Hundra gånger större numeriskt värde ger ungefär tio gånger fler möjliga kandidater. Koden använder d <= n / d i stället för d*d <= n för att undvika overflow när produkten blir för stor.

Tidskomplexitet

Exempel för tidsanalys: Test av delare upp till √n.

Loopen testar möjliga delare tills d × d skulle överstiga n, eller tills en delare hittas. Villkoret d <= n / d undviker overflow från d*d för stora heltal. Sammansatta tal med små faktorer kan ge snabbare avslut. Primtal nära den valda storleken ger typiskt många tester. Analysen antar konstant kostnad för heltalsaritmetik, vilket inte alltid gäller enorma heltal.

Räkna delartesterna

Varje iteration utför en begränsad mängd aritmetik: ett stoppvillkor, en restberäkning och en ökning av räknaren. Med fast stora heltal betraktas dessa som konstanta modelloperationer. Antalet möjliga kandidater är ungefär floor(√n)-1, eftersom sökningen börjar vid 2.

Du kan prova 2 separat och sedan bara udda kandidater för att minska antalet tester, men klassen förblir O(√n). Det finns också helt andra primtalsalgoritmer med andra komplexitetsgränser. Resultatet beskriver den här metoden, inte alla möjliga sätt att testa primtal.

C#

C# | SquareRoot.cs

bool IsPrime(int n)
{
    if (n < 2) return false;
    for (int d = 2; d <= n / d; d++)
        if (n % d == 0) return false;
    return true;
}

C++

C++ | square_root.cpp

bool isPrime(int n) {
    if (n < 2) return false;
    for (int d = 2; d <= n / d; ++d)
        if (n % d == 0) return false;
    return true;
}

Analys: Provdivision kräver O(√n) aritmetiska iterationer när n avser heltalets numeriska värde, inte dess bitlängd.

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

Minneskomplexitet

Exempel för minnesanalys: En buffert med √n element.

En buffert med ungefär √n element använder O(√n) extra minne. Det är ett annat exempel än själva provdivisionen, som bara behöver räknare och tillfälliga heltal och därmed O(1) extra minne. Minnesanalys räknar samtidigt lagrade celler, inte hur många värden en algoritm besöker totalt. Kontrollera gränser innan mycket stora buffertar allokeras.

Skilj mellan att prova och att lagra

Vid primtalstestningen lagras bara n, delaren d och några tillfälliga aritmetiska värden. Därför är det extra minnet Θ(1), trots att upp till ungefär √n tester kan utföras. Det separata buffertexemplet skapar faktiskt ungefär √n element som är aktiva samtidigt, vilket ger Θ(√n) extra minne.

Arrayer har i praktiken metadata, storleksgränser och krav på tillgängligt minne. En blockindelad algoritm kan använda O(√n) extra minne för blocksummor och samtidigt O(n) totalt minne inklusive den ursprungliga arrayen. Tala alltid om vilka värden som redan fanns innan funktionen anropades.

C#

C# | SquareRoot.cs

int limit = (int)Math.Sqrt(n);
int[] buffer = new int[limit];

C++

C++ | square_root.cpp

#include <vector>
#include <cmath>

int limit = static_cast<int>(std::sqrt(n));
std::vector<int> buffer(limit); // O(sqrt(n)) additional cells

Analys: En buffert på √n element använder O(√n) extra minne; provdivision i sig har O(1) extra minne.

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

Så känner du igen kvadratrotsbeteende

Sök efter en loop som stannar vid kvadratroten eller efter block som är ungefär √n stora. Kontrollera sedan noggrant vad n betyder. Vid delartestning är det talets värde; i en blockindelad array är det antalet element. Ett jämnt sammansatt tal går fort att förkasta, medan ett stort primtal kan kräva nästan alla tester.

Minnesklassen bestäms inte av antalet iterationer. En primtalskontroll kan ha O(√n) tid men O(1) extra minne; en bufferbyggare kan använda O(√n) utrymme av helt andra skäl.

Praktiskt exempel: dela mätvärden i block

Anta att en array innehåller 10 000 mätvärden. Om varje block innehåller 100 värden får vi ungefär 100 block och lika många sammanfattningar, alltså omkring √n extra poster. En intervallsumma kan beräknas genom att använda sammanfattningar för hela block och undersöka värden i högst två ofullständiga block. Med lämplig struktur kan en fråga kosta ungefär O(√n), medan uppbyggnaden av sammanfattningarna fortfarande kräver O(n) tid.

Detta är en annan användning av kvadratroten än primtalstestning: här räknar n antal arrayelement, inte ett heltals numeriska värde. Uppdateringar måste också hålla blocksummorna korrekta.

Vanligt misstag

Se upp: Blanda inte ihop O(√n) operationer i förhållande till heltalets värde med O(√b) i förhållande till en indata på b bitar. Ett b-bitars tal kan ha storleken ungefär 2^b.

Testa kunskaperna

Jämför provdivision för primtalskandidater nära 100 och nära 10 000. Räkna antalet delartester i stället för enbart tid i millisekunder.

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