Stor O-notasjon er et kraftig verktøy som brukes i informatikk for å beskrive tidskompleksiteten eller romkompleksiteten til algoritmer. Det gir en standardisert måte å sammenligne effektiviteten til forskjellige algoritmer når det gjelder deres verste ytelse. Forståelse Stor O-notasjon er avgjørende for å analysere og designe effektive algoritmer.
I denne opplæringen vil vi dekke det grunnleggende om Stor O-notasjon , dens betydning, og hvordan analysere kompleksiteten til algoritmer ved hjelp av Stor O .
Innholdsfortegnelse
- Hva er Big-O-notasjon?
- Definisjon av Big-O-notasjon:
- Hvorfor er Big O-notasjon viktig?
- Egenskaper til Big O-notasjon
- Vanlige Big-O-notasjoner
- Hvordan bestemme Big O-notasjon?
- Matematiske eksempler på kjøretidsanalyse
- Algoritmiske eksempler på kjøretidsanalyse
- Algoritmeklasser med antall operasjoner og utførelsestid
- Sammenligning av Big O-notasjon, Big Ω (Omega)-notasjon og Big θ (Theta)-notasjon
- Ofte stilte spørsmål om Big O-notasjon
Hva er Big-O-notasjon?
Big-O , ofte referert til som Bestilling av , er en måte å uttrykke øvre grense av en algoritmes tidskompleksitet, siden den analyserer verste fall algoritmens situasjon. Det gir en øvre grense på tiden en algoritme tar når det gjelder størrelsen på inngangen. Det er betegnet som O(f(n)) , hvor f(n) er en funksjon som representerer antall operasjoner (trinn) som en algoritme utfører for å løse et problem av størrelse n .
Big-O-notasjon brukes til å beskrive ytelsen eller kompleksiteten til en algoritme. Konkret beskriver den I verste fall i form av tid eller plass kompleksitet.
Viktig poeng:
- Stor O-notasjon beskriver bare den asymptotiske oppførselen til en funksjon, ikke dens eksakte verdi.
- De Stor O-notasjon kan brukes til å sammenligne effektiviteten til forskjellige algoritmer eller datastrukturer.
Definisjon av Big-O-notasjon:
Gitt to funksjoner f(n) og g(n) , sier vi det f(n) er O(g(n)) hvis det finnes konstanter c> 0 og n 0 >= 0 slik at f(n) <= c*g(n) for alle n>= n 0 .
I enklere termer, f(n) er O(g(n)) hvis f(n) vokser ikke raskere enn c*g(n) for alle n>= n0hvor c og n0er konstanter.
Hvorfor er Big O-notasjon viktig?
Big O-notasjon er en matematisk notasjon som brukes til å beskrive den verste tidskompleksiteten eller effektiviteten til en algoritme eller den verste plasskompleksiteten til en datastruktur. Det gir en måte å sammenligne ytelsen til forskjellige algoritmer og datastrukturer på, og å forutsi hvordan de vil oppføre seg når inngangsstørrelsen øker.
Big O-notasjon er viktig av flere grunner:
- Big O-notasjon er viktig fordi det hjelper til med å analysere effektiviteten til algoritmer.
- Det gir en måte å beskrive hvordan kjøretid eller plassbehov av en algoritme vokser ettersom inndatastørrelsen øker.
- Lar programmerere sammenligne forskjellige algoritmer og velge den mest effektive for et spesifikt problem.
- Hjelper med å forstå skalerbarheten til algoritmer og forutsi hvordan de vil fungere etter hvert som inngangsstørrelsen vokser.
- Gjør det mulig for utviklere å optimalisere koden og forbedre den generelle ytelsen.
Egenskaper til Big O-notasjon:
Nedenfor er noen viktige egenskaper ved Big O-notasjon:
1. Refleksivitet:
For enhver funksjon f(n), f(n) = O(f(n)).
Eksempel:
unnslippe karakter java
f(n) = n2, så f(n) = O(n2).
2. Transitivitet:
Hvis f(n) = O(g(n)) og g(n) = O(h(n)), så er f(n) = O(h(n)).
Eksempel:
f(n) = n3, g(n) = n2, h(n) = n4. Da er f(n) = O(g(n)) og g(n) = O(h(n)). Derfor er f(n) = O(h(n)).
3. Konstant faktor:
For enhver konstant c> 0 og funksjoner f(n) og g(n), hvis f(n) = O(g(n)), så cf(n) = O(g(n)).
Eksempel:
java tilfeldig tall
f(n) = n, g(n) = n2. Da er f(n) = O(g(n)). Derfor er 2f(n) = O(g(n)).
4. Sumregel:
Hvis f(n) = O(g(n)) og h(n) = O(g(n)), så er f(n) + h(n) = O(g(n)).
Eksempel:
f(n) = n2, g(n) = n3, h(n) = n4. Da er f(n) = O(g(n)) og h(n) = O(g(n)). Derfor er f(n) + h(n) = O(g(n)).
5. Produktregel:
Hvis f(n) = O(g(n)) og h(n) = O(k(n)), så f(n) * h(n) = O(g(n) * k(n)) .
Eksempel:
f(n) = n, g(n) = n2, h(n) = n3, k(n) = n4. Da er f(n) = O(g(n)) og h(n) = O(k(n)). Derfor, f(n) * h(n) = O(g(n) * k(n)) = O(n5).
6. Sammensetningsregel:
Hvis f(n) = O(g(n)) og g(n) = O(h(n)), så er f(g(n)) = O(h(n)).
Eksempel:
f(n) = n2, g(n) = n, h(n) = n3. Da er f(n) = O(g(n)) og g(n) = O(h(n)). Derfor er f(g(n)) = O(h(n)) = O(n3).
Vanlige Big-O-notasjoner:
Big-O-notasjon er en måte å måle tids- og romkompleksiteten til en algoritme. Den beskriver den øvre grensen for kompleksiteten i verste fall. La oss se nærmere på de forskjellige typene tidskompleksiteter:
1. Lineær tidskompleksitet: Stor O(n) kompleksitet
Lineær tidskompleksitet betyr at kjøretiden til en algoritme vokser lineært med størrelsen på inngangen.
Tenk for eksempel på en algoritme som går gjennom en matrise for å finne et spesifikt element :
Kodebit 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 tidskompleksitet: Stor O(log n) kompleksitet
Logaritmisk tidskompleksitet betyr at kjøretiden til en algoritme er proporsjonal med logaritmen til inngangsstørrelsen.
For eksempel, en binær søkealgoritme har en logaritmisk tidskompleksitet:
Kodebit int binarySearch(int arr[], int l, int r, int x) { if (r>= l) { int mid = l + (r - l) / 2; if (arr[midt] == x) returner midt; if (arr[midt]> x) returner binært søk(arr, l, mid - 1, x); return binarySearch(arr, mid + 1, r, x); } returner -1; }> 3. Kvadratisk tidskompleksitet: Stor O(n2) Kompleksitet
Kvadratisk tidskompleksitet betyr at kjøretiden til en algoritme er proporsjonal med kvadratet på inngangsstørrelsen.
For eksempel en enkel boblesorteringsalgoritme har en kvadratisk tidskompleksitet:
Kodebit 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. Kubikktidskompleksitet: Stor O(n3) Kompleksitet
Kubisk tidskompleksitet betyr at kjøretiden til en algoritme er proporsjonal med kuben til inngangsstørrelsen.
For eksempel en naiv matrisemultiplikasjonsalgoritme har en kubikktidskompleksitet:
Kodebit 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. Polynomisk tidskompleksitet: Stor O(nk) Kompleksitet
Polynomisk tidskompleksitet refererer til tidskompleksiteten til en algoritme som kan uttrykkes som en polynomfunksjon av inngangsstørrelsen n . I Big O notasjon, sies en algoritme å ha polynomisk tidskompleksitet hvis tidskompleksiteten er det På k ) , hvor k er en konstant og representerer graden av polynomet.
Algoritmer med polynomisk tidskompleksitet anses generelt som effektive, ettersom kjøretiden vokser med en rimelig hastighet etter hvert som inngangsstørrelsen øker. Vanlige eksempler på algoritmer med polynomisk tidskompleksitet inkluderer lineær tidskompleksitet O(n) , kvadratisk tidskompleksitet O(n 2 ) , og kubikktidskompleksitet O(n 3 ) .
6. Eksponentiell tidskompleksitet: Stor O(2n) Kompleksitet
Eksponentiell tidskompleksitet betyr at kjøretiden til en algoritme dobles med hvert tillegg til inndatasettet.
For eksempel problemet med generere alle delmengder av et sett har eksponentiell tidskompleksitet:
Kodebit 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 tidskompleksitet: Stor O(n!) kompleksitet
Faktoriell tidskompleksitet betyr at kjøretiden til en algoritme vokser faktorielt med størrelsen på inngangen. Dette sees ofte i algoritmer som genererer alle permutasjoner av et sett med data.
Her er et eksempel på en faktoriell tidskompleksitetsalgoritme, som genererer alle permutasjoner av en matrise:
Kodebit 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 } } }> Hvis vi plotter de vanligste Big O-notasjonseksemplene, vil vi ha en graf slik:
Hvordan bestemme Big O-notasjon?
Stor O-notasjon er en matematisk notasjon som brukes til å beskrive asymptotisk oppførsel av en funksjon ettersom dens input vokser uendelig stor. Det gir en måte å karakterisere effektiviteten til algoritmer og datastrukturer.
hvordan konvertere int til streng java
Trinn for å bestemme Big O-notasjon:
1. Identifiser den dominerende termen:
- Undersøk funksjonen og identifiser begrepet med den høyeste vekstorden etter hvert som inputstørrelsen øker.
- Ignorer eventuelle konstante faktorer eller termer av lavere orden.
2. Bestem rekkefølgen for vekst:
- Rekkefølgen av vekst av den dominerende termen bestemmer Big O-notasjonen.
3. Skriv Big O-notasjonen:
- Big O-notasjonen skrives som O(f(n)), der f(n) representerer det dominerende leddet.
- For eksempel, hvis den dominerende termen er n^2, vil Big O-notasjonen være O(n^2).
4. Forenkle notasjonen (valgfritt):
- I noen tilfeller Big O merkevarebygging n kan forenkles ved å fjerne konstante faktorer eller ved å bruke en mer kortfattet notasjon.
- For eksempel, O(2n) kan forenkles til På).
Eksempel:
Funksjon: f(n) = 3n3+ 2n2+ 5n + 1
- Dominant Term: 3n3
- Vekstorden: kubikk (n3)
- Stor O-notasjon: O(n3)
- Forenklet notasjon: O(n3)
Matematiske eksempler på kjøretidsanalyse:
Tabellen nedenfor illustrerer kjøretidsanalysen av forskjellige rekkefølger av algoritmer når inngangsstørrelsen (n) øker.
| n | logg(n) | n | n * log(n) | n^2 | 2^n | n! |
|---|---|---|---|---|---|---|
| 10 | 1 | 10 | 10 | 100 | 1024 | 3628800 |
| tjue | 2.996 | tjue | 59,9 | 400 | 1048576 | 2.432902e+1818 |
Algoritmiske eksempler på kjøretidsanalyse:
Tabellen nedenfor kategoriserer algoritmer basert på deres kjøretidskompleksitet og gir eksempler for hver type.
| Type | Notasjon | Eksempel algoritmer |
|---|---|---|
| Logaritmisk | O(log n) | Binært søk |
| Lineær | På) | Lineært søk |
| Superlineær | O(n log n) | Heap Sorter, Merge Sorter |
| Polynom | O(n^c) | Strassens matrisemultiplikasjon, boblesortering, utvalgssortering, innsettingssortering, bøttesortering |
| Eksponentiell | O(c^n) | Tårnet i Hanoi |
| Faktoriell | På!) | Determinant utvidelse av mindreårige, Brute force Søkealgoritme for Traveling Salesman Problem |
Algoritmeklasser med antall operasjoner og utførelsestid:
Nedenfor er klassene av algoritmer og deres utførelsestider på en datamaskin som kjører 1 million operasjoner per sekund (1 sek = 10 6 μsek = 10 3 msek) :
Store O-notasjonsklasser | f(n) | Big O-analyse (antall operasjoner) for n = 10 | Utførelsestid (1 instruksjon/μsek) |
|---|---|---|---|
konstant | O(1) | 1 | 1 μsek |
logaritmisk | O(logg) | 3,32 | 3 μsek |
lineær | På) | 10 | 10 μsek knappen for å sentrere css |
O(nlogn) | O(nlogn) | 33.2 | 33 μsek |
kvadratisk | På2) | 102 | 100 μsek |
kubikk | På3) | 103 | 1 msek |
eksponentiell | O(2n) | 1024 | 10 msek css bryte tekst |
faktoriell | På!) | 10! | 3,6288 sek |
Sammenligning av Big O-notasjon, Big Ω (Omega)-notasjon og Big θ (Theta)-notasjon:
Nedenfor er en tabell som sammenligner Big O-notasjon, Ω (Omega)-notasjon og θ (Theta)-notasjon:
| Notasjon | Definisjon | Forklaring |
|---|---|---|
| Stor O (O) | f(n) ≤ C * g(n) for alle n ≥ n0 | Beskriver den øvre grensen for algoritmens kjøretid i verste fall . |
| Ω (Omega) | f(n) ≥ C * g(n) for alle n ≥ n0 | Beskriver den nedre grensen for algoritmens kjøretid i beste tilfelle . |
| θ (Theta) | C1* g(n) ≤ f(n) ≤ C2* g(n) for n ≥ n0 | Beskriver både øvre og nedre grenser for algoritmen driftstid . |
I hver notasjon:
- f(n) representerer funksjonen som analyseres, typisk algoritmens tidskompleksitet.
- g(n) representerer en spesifikk funksjon som begrenser f(n) .
- C, C1, og C2 er konstanter.
- n 0 er den minste inngangsstørrelsen som ulikheten holder utover.
Disse notasjonene brukes til å analysere algoritmer basert på deres verste fall (Big O) , beste tilfelle (Ω) , og gjennomsnittlig tilfelle (θ) scenarier.
Ofte stilte spørsmål om Big O-notasjon:
Spørsmål 1. Hva er Big O-notasjon?
Svar: Big O Notation er en matematisk notasjon som brukes til å beskrive den øvre grensen for en algoritmes tidskompleksitet når det gjelder hvordan den vokser i forhold til størrelsen på input.
Spørsmål 2. Hvorfor er Big O-notasjon viktig?
Svar: Det hjelper oss å analysere og sammenligne effektiviteten til algoritmer ved å fokusere på det verste tilfellet og forstå hvordan ytelsen deres skalerer med inputstørrelse.
Spørsmål 3. Hvordan beregnes Big O-notasjon?
Svar: Big O-notasjon bestemmes ved å identifisere den dominerende operasjonen i en algoritme og uttrykke dens tidskompleksitet i form av n, der n representerer inngangsstørrelsen.
Spørsmål 4. Hva betyr O(1) i Big O-notasjon?
Svar: O(1) betyr konstant tidskompleksitet, noe som indikerer at en algoritmes utførelsestid ikke endres uavhengig av inngangsstørrelsen.
Spørsmål 5. Hva er betydningen av forskjellige Big O-kompleksiteter som O(log n) eller O(n^2)?
Svar: Ulike kompleksiteter som O(log n) eller O(n^2) representerer hvordan ytelsen til en algoritme skaleres etter hvert som inngangsstørrelsen øker, og gir innsikt i effektiviteten og skalerbarheten.
Spørsmål 6. Kan Big O-notasjon også brukes på romkompleksitet?
Svar: Ja, Big O Notation kan også brukes til å analysere og beskrive en algoritmes plasskompleksitet, og indikerer hvor mye minne den krever i forhold til inngangsstørrelsen.
Relatert artikkel:
- Eksempler på Big-O-analyse
- Design og analyse av algoritmer
- Typer asymptotiske notasjoner i kompleksitetsanalyse av algoritmer
- Analyse av algoritmer | Stor – Ω (Big- Omega) notasjon
- Analyse av algoritmer | lite o og lite omega-notasjoner