Grote O-notatie is een krachtig hulpmiddel dat in de computerwetenschappen wordt gebruikt om de tijdscomplexiteit of ruimtecomplexiteit van algoritmen te beschrijven. Het biedt een gestandaardiseerde manier om de efficiëntie van verschillende algoritmen te vergelijken in termen van hun slechtste prestaties. Begrip Grote O-notatie is essentieel voor het analyseren en ontwerpen van efficiënte algoritmen.

In deze tutorial behandelen we de basisprincipes van Grote O-notatie , de betekenis ervan, en hoe de complexiteit van algoritmen kan worden geanalyseerd Grote O .

Inhoudsopgave

• Wat is Big-O-notatie?
• Definitie van Big-O-notatie:
• Waarom is Big O-notatie belangrijk?
• Eigenschappen van Big O-notatie
• Veel voorkomende Big-O-notaties
• Hoe bepaal je de Big O-notatie?
• Wiskundige voorbeelden van runtime-analyse
• Algoritmische voorbeelden van runtime-analyse
• Algoritmeklassen met aantal bewerkingen en uitvoeringstijd
• Vergelijking van Big O-notatie, Big Ω (Omega)-notatie en Big θ (Theta)-notatie
• Veelgestelde vragen over Big O-notatie

Wat is Big-O-notatie?

Big-O , gewoonlijk aangeduid als Volgorde van , is een manier om de bovengrens van de tijdscomplexiteit van een algoritme, omdat het de het slechtste geval situatie van algoritme. Het biedt een bovengrens op de tijd die een algoritme nodig heeft in termen van de grootte van de invoer. Het wordt aangeduid als O(f(n)) , waar f(n) is een functie die het aantal bewerkingen (stappen) vertegenwoordigt dat een algoritme uitvoert om een ​​probleem van omvang op te lossen N .

Big-O-notatie wordt gebruikt om de prestaties of complexiteit van een algoritme te beschrijven. Concreet beschrijft het de in het slechtste geval aangaande met tijd of complexiteit van de ruimte.

Belangrijk punt:

• Grote O-notatie beschrijft alleen het asymptotische gedrag van een functie, niet de exacte waarde ervan.
• De Grote O-notatie kan worden gebruikt om de efficiëntie van verschillende algoritmen of datastructuren te vergelijken.

Definitie van Big-O-notatie:

Gegeven twee functies f(n) En g(n) , dat zeggen wij f(n) is O(g(n)) als er constanten bestaan c> 0 En N ₀ >= 0 zodanig dat f(n) <= c*g(n) voor iedereen n>= n ₀ .

In eenvoudiger bewoordingen: f(n) is O(g(n)) als f(n) groeit niet sneller dan c*g(n) voor alle n>= n₀waarbij c en n₀zijn constanten.

Waarom is Big O-notatie belangrijk?

Big O-notatie is een wiskundige notatie die wordt gebruikt om de slechtste tijdscomplexiteit of efficiëntie van een algoritme of de slechtste ruimtecomplexiteit van een datastructuur te beschrijven. Het biedt een manier om de prestaties van verschillende algoritmen en datastructuren te vergelijken, en om te voorspellen hoe ze zich zullen gedragen naarmate de invoer groter wordt.

Big O-notatie is om verschillende redenen belangrijk:

• Big O Notation is belangrijk omdat het helpt bij het analyseren van de efficiëntie van algoritmen.
• Het biedt een manier om te beschrijven hoe de looptijd of ruimtevereisten van een algoritme groeit naarmate de invoer groter wordt.
• Hiermee kunnen programmeurs verschillende algoritmen vergelijken en de meest efficiënte voor een specifiek probleem kiezen.
• Helpt bij het begrijpen van de schaalbaarheid van algoritmen en het voorspellen van hoe ze zullen presteren naarmate de invoergrootte groeit.
• Stelt ontwikkelaars in staat code te optimaliseren en de algehele prestaties te verbeteren.

Eigenschappen van Big O-notatie:

Hieronder staan ​​enkele belangrijke eigenschappen van Big O Notation:

1. Reflexiviteit:

Voor elke functie f(n), f(n) = O(f(n)).

Voorbeeld:

f(n) = n², dan f(n) = O(n²).

2. Transitiviteit:

Als f(n) = O(g(n)) en g(n) = O(h(n)), dan f(n) = O(h(n)).

Voorbeeld:

f(n) = n³, g(n) = n², h(n) = n⁴. Dan is f(n) = O(g(n)) en g(n) = O(h(n)). Daarom f(n) = O(h(n)).

3. Constante factor:

Voor elke constante c> 0 en functies f(n) en g(n), als f(n) = O(g(n)), dan cf(n) = O(g(n)).

Voorbeeld:

f(n) = n, g(n) = n². Dan is f(n) = O(g(n)). Daarom is 2f(n) = O(g(n)).

4. Somregel:

Als f(n) = O(g(n)) en h(n) = O(g(n)), dan f(n) + h(n) = O(g(n)).

Voorbeeld:

f(n) = n², g(n) = n³, h(n) = n⁴. Dan is f(n) = O(g(n)) en h(n) = O(g(n)). Daarom f(n) + h(n) = O(g(n)).

5. Productregel:

Als f(n) = O(g(n)) en h(n) = O(k(n)), dan f(n) * h(n) = O(g(n) * k(n)) .

Voorbeeld:

f(n) = n, g(n) = n², h(n) = n³, k(n) = n⁴. Dan is f(n) = O(g(n)) en h(n) = O(k(n)). Daarom f(n) * h(n) = O(g(n) * k(n)) = O(n)⁵).

6. Samenstellingsregel:

Als f(n) = O(g(n)) en g(n) = O(h(n)), dan f(g(n)) = O(h(n)).

Voorbeeld:

f(n) = n², g(n) = n, h(n) = n³. Dan is f(n) = O(g(n)) en g(n) = O(h(n)). Daarom geldt f(g(n)) = O(h(n)) = O(n).³).

Veel voorkomende Big-O-notaties:

Big-O-notatie is een manier om de tijd- en ruimtecomplexiteit van een algoritme te meten. Het beschrijft de bovengrens van de complexiteit in het worstcasescenario. Laten we eens kijken naar de verschillende soorten tijdcomplexiteit:

1. Lineaire tijdcomplexiteit: Big O(n)-complexiteit

Lineaire tijdscomplexiteit betekent dat de looptijd van een algoritme lineair groeit met de omvang van de invoer.

Neem bijvoorbeeld een algoritme dat doorkruist een array om een ​​specifiek element te vinden :

bool findElement(int arr[], int n, int key) {  for (int i = 0; i < n; i++) {  if (arr[i] == key) {  return true;  }  }  return false; }>

2. Logaritmische tijdscomplexiteit: Big O(log n) complexiteit

Logaritmische tijdscomplexiteit betekent dat de looptijd van een algoritme evenredig is aan de logaritme van de invoergrootte.

string naar geheel getal in Java

Bijvoorbeeld, een binair zoekalgoritme heeft een logaritmische tijdscomplexiteit:

int binarySearch(int arr[], int l, int r, int x) {  if (r>= l) { int midden = l + (r - l) / 2;  als (arr[mid] == x) midden terugkeert;  if (arr[mid]> x) retourneert binarySearch(arr, l, mid - 1, x);  return binarySearch(arr, mid + 1, r, x);  } retourneer -1; }>

3. Kwadratische tijdcomplexiteit: Big O(n²) Complexiteit

Kwadratische tijdscomplexiteit betekent dat de looptijd van een algoritme evenredig is met het kwadraat van de invoergrootte.

Een simpele bijvoorbeeld algoritme voor het sorteren van bellen heeft een kwadratische tijdscomplexiteit:

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. Kubieke tijdcomplexiteit: Big O(n³) Complexiteit

Kubieke tijdcomplexiteit betekent dat de looptijd van een algoritme evenredig is aan de kubus van de invoergrootte.

Een naïef bijvoorbeeld algoritme voor matrixvermenigvuldiging heeft een kubieke tijdscomplexiteit:

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. Polynomiale tijdscomplexiteit: Big O(n^k) Complexiteit

Polynomiale tijdscomplexiteit verwijst naar de tijdscomplexiteit van een algoritme die kan worden uitgedrukt als een polynomiale functie van de invoergrootte N . In Groot O In de notatie wordt gezegd dat een algoritme een polynomiale tijdscomplexiteit heeft als de tijdscomplexiteit dat is Op ^k ) , waar k is een constante en vertegenwoordigt de graad van de polynoom.

Algoritmen met polynomiale tijdscomplexiteit worden over het algemeen als efficiënt beschouwd, aangezien de looptijd redelijk snel groeit naarmate de invoergrootte toeneemt. Veel voorkomende voorbeelden van algoritmen met polynomiale tijdscomplexiteit zijn onder meer: lineaire tijdcomplexiteit O(n) , kwadratische tijdscomplexiteit O(n ² ) , En kubieke tijdscomplexiteit O(n ³ ) .

6. Exponentiële tijdscomplexiteit: Big O(2^N) Complexiteit

Exponentiële tijdscomplexiteit betekent dat de looptijd van een algoritme verdubbelt bij elke toevoeging aan de invoergegevensset.

Het probleem van bijvoorbeeld het genereren van alle subsets van een set is van exponentiële tijdscomplexiteit:

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;  } }>

Factoriële tijdcomplexiteit: Big O(n!) Complexiteit

Factoriële tijdscomplexiteit betekent dat de looptijd van een algoritme factorieel groeit met de grootte van de invoer. Dit wordt vaak gezien in algoritmen die alle permutaties van een reeks gegevens genereren.

Hier is een voorbeeld van een algoritme voor factoriële tijdcomplexiteit, dat alle permutaties van een array genereert:

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  }  } }>

Als we de meest voorkomende voorbeelden van Big O-notaties zouden plotten, zouden we een grafiek als deze krijgen:

Hoe bepaal je de Big O-notatie?

Grote O-notatie is een wiskundige notatie die wordt gebruikt om de asymptotisch gedrag van een functie naarmate de invoer ervan oneindig groot wordt. Het biedt een manier om de efficiëntie van algoritmen en datastructuren te karakteriseren.

Stappen om de Big O-notatie te bepalen:

1. Identificeer de dominante term:

• Onderzoek de functie en identificeer de term met de hoogste groeiorde naarmate de invoer groter wordt.
• Negeer alle constante factoren of termen van lagere orde.

2. Bepaal de volgorde van groei:

• De volgorde van groei van de dominante term bepaalt de Big O-notatie.

3. Schrijf de Big O-notatie:

• De Big O-notatie wordt geschreven als O(f(n)), waarbij f(n) de dominante term vertegenwoordigt.
• Als de dominante term bijvoorbeeld n^2 is, zou de Big O-notatie O(n^2) zijn.

4. Vereenvoudig de notatie (optioneel):

• In sommige gevallen is de Big O-merk n kan worden vereenvoudigd door constante factoren te verwijderen of door een beknoptere notatie te gebruiken.
• Bijvoorbeeld, O(2n) kan worden vereenvoudigd tot Op).

Voorbeeld:

Functie: f(n) = 3n³+ 2n²+ 5n + 1

1. Dominante term: 3n³
2. Volgorde van groei: Kubisch (n³)
3. Grote O-notatie: O(n³)
4. Vereenvoudigde notatie: O(n³)

Wiskundige voorbeelden van runtime-analyse:

Onderstaande tabel illustreert de runtime-analyse van verschillende ordes van algoritmen naarmate de invoergrootte (n) toeneemt.

Algoritmische voorbeelden van runtime-analyse:

De onderstaande tabel categoriseert algoritmen op basis van hun runtime-complexiteit en geeft voorbeelden voor elk type.

Algoritmeklassen met aantal bewerkingen en uitvoeringstijd:

Hieronder staan ​​de klassen van algoritmen en hun uitvoeringstijden op een computer die wordt uitgevoerd 1 miljoen handelingen per seconde (1 sec = 10 ⁶ μsec = 10 ³ msec) :

Vergelijking van Big O-notatie, Big Ω (Omega)-notatie en Big θ (Theta)-notatie:

Hieronder staat een tabel waarin de Big O-notatie, Ω (Omega)-notatie en θ (Theta)-notatie worden vergeleken:

In elke notatie:

oneindige lus

• f(n) vertegenwoordigt de functie die wordt geanalyseerd, doorgaans de tijdscomplexiteit van het algoritme.
• g(n) vertegenwoordigt een specifieke functie die grenst f(n) .
• C, C1​, En C2 zijn constanten.
• N ₀ ​ is de minimale invoergrootte waarboven de ongelijkheid geldt.

Deze notaties worden gebruikt om algoritmen te analyseren op basis van hun in het slechtste geval (Big O) , beste geval (Ω) , En gemiddeld geval (θ) scenario's.

Veelgestelde vragen over Big O-notatie:

Vraag 1. Wat is Big O-notatie?

Antwoord: Big O Notation is een wiskundige notatie die wordt gebruikt om de bovengrens van de tijdscomplexiteit van een algoritme te beschrijven in termen van hoe deze groeit ten opzichte van de omvang van de invoer.

Vraag 2. Waarom is Big O-notatie belangrijk?

Antwoord: Het helpt ons de efficiëntie van algoritmen te analyseren en te vergelijken door ons te concentreren op het worstcasescenario en te begrijpen hoe hun prestaties schalen met de invoergrootte.

Vraag 3. Hoe wordt Big O Notation berekend?

Antwoord: Big O-notatie wordt bepaald door de dominante bewerking in een algoritme te identificeren en de tijdscomplexiteit ervan uit te drukken in termen van n, waarbij n de invoergrootte vertegenwoordigt.

Vraag 4. Wat betekent O(1) in de Big O-notatie?

Antwoord: O(1) betekent constante tijdscomplexiteit, wat aangeeft dat de uitvoeringstijd van een algoritme niet verandert, ongeacht de invoergrootte.

Vraag 5. Wat is de betekenis van verschillende Big O-complexiteiten zoals O(log n) of O(n^2)?

Antwoord: Verschillende complexiteiten zoals O(log n) of O(n^2) geven weer hoe de prestaties van een algoritme schalen naarmate de invoergrootte toeneemt, wat inzicht geeft in de efficiëntie en schaalbaarheid ervan.

Vraag 6. Kan Big O Notation ook worden toegepast op ruimtecomplexiteit?

Antwoord: Ja, Big O Notation kan ook worden gebruikt om de ruimtecomplexiteit van een algoritme te analyseren en te beschrijven, waarbij wordt aangegeven hoeveel geheugen het nodig heeft in verhouding tot de invoergrootte.

Gerelateerd artikel:

• Voorbeelden van Big-O-analyse
• Ontwerp en analyse van algoritmen
• Soorten asymptotische notaties bij de complexiteitsanalyse van algoritmen
• Analyse van algoritmen | Big – Ω (Big-Omega) notatie
• Analyse van algoritmen | kleine o- en kleine omega-notaties