Stor O-notation är ett kraftfullt verktyg som används inom datavetenskap för att beskriva tidskomplexiteten eller rymdkomplexiteten hos algoritmer. Det ger ett standardiserat sätt att jämföra effektiviteten hos olika algoritmer när det gäller deras prestanda i värsta fall. Förståelse Stor O-notation är avgörande för att analysera och designa effektiva algoritmer.
I den här handledningen kommer vi att täcka grunderna i Stor O-notation , dess betydelse och hur man analyserar komplexiteten hos algoritmer med hjälp av Stora O .
Innehållsförteckning
python sortering tuplar
- Vad är Big-O Notation?
- Definition av Big-O Notation:
- Varför är Big O Notation viktigt?
- Egenskaper för Big O Notation
- Vanliga Big-O-notationer
- Hur bestämmer man Big O-notation?
- Matematiska exempel på körtidsanalys
- Algoritmiska exempel på körtidsanalys
- Algoritmklasser med antal operationer och exekveringstid
- Jämförelse av Big O notation, Big Ω (Omega) notation och Big θ (Theta) notation
- Vanliga frågor om Big O Notation
Vad är Big-O Notation?
Big-O , vanligen kallad Beställning av , är ett sätt att uttrycka övre gräns av en algoritms tidskomplexitet, eftersom den analyserar värsta fall algoritmens situation. Det ger en övre gräns på den tid som en algoritm tar när det gäller storleken på inmatningen. Det betecknas som O(f(n)) , var f(n) är en funktion som representerar antalet operationer (steg) som en algoritm utför för att lösa ett storleksproblem n .
Big-O notation används för att beskriva prestanda eller komplexitet hos en algoritm. Specifikt beskriver den i värsta fall i form av tid eller rymdkomplexitet.
Viktig poäng:
- Stor O-notation beskriver bara det asymptotiska beteendet hos en funktion, inte dess exakta värde.
- De Stor O-notation kan användas för att jämföra effektiviteten hos olika algoritmer eller datastrukturer.
Definition av Big-O Notation:
Givet två funktioner f(n) och g(n) , det säger vi f(n) är O(g(n)) om det finns konstanter c> 0 och n 0 >= 0 sånt f(n) <= c*g(n) för alla n>= n 0 .
I enklare termer, f(n) är O(g(n)) om f(n) växer inte snabbare än c*g(n) för alla n>= n0där c och n0är konstanter.
Varför är Big O Notation viktigt?
Big O-notation är en matematisk notation som används för att beskriva den värsta tänkbara tidskomplexiteten eller effektiviteten hos en algoritm eller den värsta tänkbara rymdkomplexiteten i en datastruktur. Det ger ett sätt att jämföra prestanda för olika algoritmer och datastrukturer, och att förutsäga hur de kommer att bete sig när indatastorleken ökar.
Stor O-notation är viktig av flera anledningar:
- Big O Notation är viktigt eftersom det hjälper till att analysera effektiviteten hos algoritmer.
- Det ger ett sätt att beskriva hur körning eller utrymmeskrav av en algoritm växer när indatastorleken ökar.
- Tillåter programmerare att jämföra olika algoritmer och välja den mest effektiva för ett specifikt problem.
- Hjälper till att förstå skalbarheten hos algoritmer och förutsäga hur de kommer att prestera när indatastorleken växer.
- Gör det möjligt för utvecklare att optimera koden och förbättra den övergripande prestandan.
Egenskaper för Big O-notation:
Nedan är några viktiga egenskaper hos Big O-notation:
1. Reflexivitet:
För vilken funktion f(n) som helst, f(n) = O(f(n)).
Exempel:
f(n) = n2, då f(n) = O(n2).
2. Transitivitet:
Om f(n) = O(g(n)) och g(n) = O(h(n)), så är f(n) = O(h(n)).
Exempel:
f(n) = n3, g(n) = n2h(n) = n4. Då är f(n) = O(g(n)) och g(n) = O(h(n)). Därför är f(n) = O(h(n)).
3. Konstant faktor:
För varje konstant c> 0 och funktioner f(n) och g(n), om f(n) = O(g(n)), då cf(n) = O(g(n)).
Exempel:
f(n) = n, g(n) = n2. Då är f(n) = O(g(n)). Därför är 2f(n) = O(g(n)).
4. Summaregel:
Om f(n) = O(g(n)) och h(n) = O(g(n)), då f(n) + h(n) = O(g(n)).
Exempel:
f(n) = n2, g(n) = n3h(n) = n4. Då är f(n) = O(g(n)) och h(n) = O(g(n)). Därför är f(n) + h(n) = O(g(n)).
5. Produktregel:
Om f(n) = O(g(n)) och h(n) = O(k(n)), då f(n) * h(n) = O(g(n) * k(n)) .
Exempel:
f(n) = n, g(n) = n2h(n) = n3k(n) = n4. Då är f(n) = O(g(n)) och h(n) = O(k(n)). Därför f(n) * h(n) = O(g(n) * k(n)) = O(n5).
6. Kompositionsregel:
Om f(n) = O(g(n)) och g(n) = O(h(n)), så är f(g(n)) = O(h(n)).
Exempel:
f(n) = n2, g(n) = n, h(n) = n3. Då är f(n) = O(g(n)) och g(n) = O(h(n)). Därför är f(g(n)) = O(h(n)) = O(n3).
Vanliga Big-O-notationer:
Big-O-notation är ett sätt att mäta tids- och rumskomplexiteten hos en algoritm. Den beskriver den övre gränsen för komplexiteten i det värsta scenariot. Låt oss titta på de olika typerna av tidskomplexitet:
1. Linjär tidskomplexitet: Big O(n) komplexitet
Linjär tidskomplexitet innebär att körtiden för en algoritm växer linjärt med storleken på ingången.
Tänk till exempel en algoritm som går genom en array för att hitta ett specifikt element :
Kodavsnitt bool findElement(int arr[], int n, int key) { for (int i = 0; i < n; i++) { if (arr[i] == key) { return true; } } return false; }> 2. Logaritmisk tidskomplexitet: Stor O(log n) komplexitet
Logaritmisk tidskomplexitet innebär att körtiden för en algoritm är proportionell mot logaritmen för indatastorleken.
Till exempel, en binär sökalgoritm har en logaritmisk tidskomplexitet:
Kodavsnitt int binarySearch(int arr[], int l, int r, int x) { if (r>= l) {int mid = l + (r - l) / 2; if (arr[mid] == x) returnera mitt; if (arr[mid]> x) returnerar binarySearch(arr, l, mid - 1, x); return binarySearch(arr, mid + 1, r, x); } returnera -1; }> 3. Kvadratisk tidskomplexitet: Stor O(n2) Komplexitet
Kvadratisk tidskomplexitet innebär att körtiden för en algoritm är proportionell mot kvadraten på indatastorleken.
Till exempel en enkel bubbelsorteringsalgoritm har en kvadratisk tidskomplexitet:
Kodavsnitt void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { swap(&arr[j], &arr[j + 1]); } } } }> 4. Kubiktidskomplexitet: Stor O(n3) Komplexitet
Kubiktidskomplexitet innebär att körtiden för en algoritm är proportionell mot kuben för indatastorleken.
Till exempel en naiv matrismultiplikationsalgoritm har en kubiktidskomplexitet:
Kodavsnitt void multiply(int mat1[][N], int mat2[][N], int res[][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { res[i][j] = 0; for (int k = 0; k < N; k++) res[i][j] += mat1[i][k] * mat2[k][j]; } } }> 5. Polynom tidskomplexitet: Big O(nk) Komplexitet
Polynom tidskomplexitet hänvisar till tidskomplexiteten hos en algoritm som kan uttryckas som en polynomfunktion av indatastorleken n . I Big O notation, sägs en algoritm ha polynomisk tidskomplexitet om dess tidskomplexitet är det På k ) , var k är en konstant och representerar graden av polynomet.
Algoritmer med polynom tidskomplexitet anses generellt vara effektiva, eftersom körtiden växer i rimlig takt när indatastorleken ökar. Vanliga exempel på algoritmer med polynom tidskomplexitet inkluderar linjär tidskomplexitet O(n) , kvadratisk tidskomplexitet O(n 2 ) , och kubiktidskomplexitet O(n 3 ) .
6. Exponentiell tidskomplexitet: Big O(2n) Komplexitet
Exponentiell tidskomplexitet innebär att körtiden för en algoritm fördubblas med varje tillägg till indatauppsättningen.
Till exempel problemet med genererar alla delmängder av en uppsättning har exponentiell tidskomplexitet:
Kodavsnitt void generateSubsets(int arr[], int n) { for (int i = 0; i < (1 << n); i++) { for (int j = 0; j < n; j++) { if (i & (1 << j)) { cout << arr[j] << ' '; } } cout << endl; } }> Faktoriell tidskomplexitet: Stor O(n!) Komplexitet
Faktoriell tidskomplexitet innebär att körtiden för en algoritm växer faktoriellt med storleken på inmatningen. Detta ses ofta i algoritmer som genererar alla permutationer av en uppsättning data.
Här är ett exempel på en faktoriell tidskomplexitetsalgoritm, som genererar alla permutationer av en array:
Kodavsnitt void permute(int* a, int l, int r) { if (l == r) { for (int i = 0; i <= r; i++) { cout << a[i] << ' '; } cout << endl; } else { for (int i = l; i <= r; i++) { swap(a[l], a[i]); permute(a, l + 1, r); swap(a[l], a[i]); // backtrack } } }> Om vi plottar de vanligaste Big O-notationsexemplen, skulle vi ha en graf så här:
Hur bestämmer man Big O-notation?
Stor O-notation är en matematisk notation som används för att beskriva asymptotiskt beteende av en funktion när dess input växer oändligt stor. Det ger ett sätt att karakterisera effektiviteten hos algoritmer och datastrukturer.
Steg för att bestämma Big O-notation:
1. Identifiera den dominerande termen:
- Undersök funktionen och identifiera termen med den högsta tillväxtordningen när insatsstorleken ökar.
- Ignorera eventuella konstanta faktorer eller termer av lägre ordning.
2. Bestäm tillväxtordningen:
- Tillväxtordningen för den dominerande termen bestämmer Big O-notationen.
3. Skriv Big O-notationen:
- Big O-notationen skrivs som O(f(n)), där f(n) representerar den dominerande termen.
- Till exempel, om den dominerande termen är n^2, skulle Big O-notationen vara O(n^2).
4. Förenkla notationen (valfritt):
konvertera från sträng till heltals java
- I vissa fall Big O-märke n kan förenklas genom att ta bort konstanta faktorer eller genom att använda en mer koncis notation.
- Till exempel, O(2n) kan förenklas till På).
Exempel:
Funktion: f(n) = 3n3+ 2n2+ 5n + 1
- Dominant term: 3n3
- Tillväxtordning: Kubisk (n3)
- Big O-notation: O(n3)
- Förenklad notation: O(n3)
Matematiska exempel på körtidsanalys:
Tabellen nedan illustrerar körtidsanalysen av olika ordningsföljder av algoritmer när indatastorleken (n) ökar.
| n | log(n) | n | n * log(n) | n^2 | 2^n | n! |
|---|---|---|---|---|---|---|
| 10 | 1 | 10 | 10 | 100 | 1024 | 3628800 |
| tjugo | 2 996 | tjugo | 59,9 | 400 | 1048576 | 2.432902e+1818 |
Algoritmiska exempel på körtidsanalys:
Tabellen nedan kategoriserar algoritmer baserat på deras runtime-komplexitet och ger exempel för varje typ.
| Typ | Notation | Exempel algoritmer |
|---|---|---|
| Logaritmisk | O(log n) | Binär sökning |
| Linjär | På) | Linjär sökning |
| Superlinjär | O(n log n) | Högsortering, sammanslagningssortering |
| Polynom | O(n^c) | Strassens matrismultiplikation, bubbelsortering, urvalssortering, infogningssortering, hinksortering |
| Exponentiell | O(c^n) | Hanois torn |
| Faktoriell | På!) | Determinant expansion av minderåriga, brute force sökalgoritm för resande säljare Problem |
Algoritmklasser med antal operationer och exekveringstid:
Nedan är klasserna av algoritmer och deras exekveringstider på en dator som exekverar 1 miljon operationer per sekund (1 sek = 10 6 μsek = 10 3 msek) :
Stora O-notationsklasser | f(n) | Big O-analys (antal operationer) för n = 10 | Utförandetid (1 instruktion/μs) |
|---|---|---|---|
konstant | O(1) | 1 | 1 μsek |
logaritmisk | O(logn) | 3,32 | 3 μsek |
linjär | På) | 10 | 10 μsek |
O(nlogn) | O(nlogn) | 33.2 | 33 μsek |
kvadratisk | På2) | 102 | 100 μsek |
kubisk | På3) | 103 | 1 msek |
exponentiell | O(2n) | 1024 | 10 msek |
faktoriellt | På!) | 10! | 3,6288 sek |
Jämförelse av Big O notation, Big Ω (Omega) notation och Big θ (Theta) notation:
Nedan finns en tabell som jämför Big O notation, Ω (Omega) notation och θ (Theta) notation:
| Notation | Definition | Förklaring |
|---|---|---|
| Stort O (O) | f(n) ≤ C * g(n) för alla n ≥ n0 | Beskriver den övre gränsen för algoritmens körtid i värsta fall . |
| Ω (Omega) | f(n) ≥ C * g(n) för alla n ≥ n0 | Beskriver den nedre gränsen för algoritmens körtid i bästa fall . |
| θ (Theta) | C1* g(n) ≤ f(n) ≤ C2* g(n) för n ≥ n0 | Beskriver både de övre och nedre gränserna för algoritmens körtid . |
I varje notation:
- f(n) representerar funktionen som analyseras, vanligtvis algoritmens tidskomplexitet.
- g(n) representerar en specifik funktion som begränsar f(n) .
- C, C1, och C2 är konstanter.
- n 0 är den minsta indatastorlek utöver vilken ojämlikheten gäller.
Dessa notationer används för att analysera algoritmer baserat på deras värsta fall (Big O) , bästa fallet (Ω) , och medel-fall (θ) scenarier.
Vanliga frågor om Big O Notation:
Fråga 1. Vad är Big O-notation?
Svar: Big O Notation är en matematisk notation som används för att beskriva den övre gränsen för en algoritms tidskomplexitet i termer av hur den växer i förhållande till storleken på inmatningen.
Fråga 2. Varför är Big O Notation viktigt?
Svar: Det hjälper oss att analysera och jämföra effektiviteten hos algoritmer genom att fokusera på det värsta scenariot och förstå hur deras prestanda skalas med indatastorlek.
Fråga 3. Hur beräknas Big O Notation?
Svar: Big O Notation bestäms genom att identifiera den dominerande operationen i en algoritm och uttrycka dess tidskomplexitet i termer av n, där n representerar indatastorleken.
Fråga 4. Vad betyder O(1) i Big O Notation?
Svar: O(1) betyder konstant tidskomplexitet, vilket indikerar att en algoritms exekveringstid inte ändras oavsett indatastorlek.
Fråga 5. Vilken betydelse har olika Big O-komplexiteter som O(log n) eller O(n^2)?
Svar: Olika komplexiteter som O(log n) eller O(n^2) representerar hur en algoritms prestanda skalas när indatastorleken ökar, vilket ger insikter om dess effektivitet och skalbarhet.
Fråga 6. Kan Big O Notation tillämpas på rymdkomplexitet också?
Svar: Ja, Big O Notation kan också användas för att analysera och beskriva en algoritms rymdkomplexitet, vilket indikerar hur mycket minne den kräver i förhållande till indatastorleken.
Relaterad artikel:
- Exempel på Big-O-analys
- Design och analys av algoritmer
- Typer av asymptotiska notationer i komplexitetsanalys av algoritmer
- Analys av algoritmer | Stor – Ω (Big- Omega) notation
- Analys av algoritmer | lite o och lite omega notationer