Stor O notation er et kraftfuldt værktøj, der bruges i datalogi til at beskrive tidskompleksiteten eller rumkompleksiteten af ​​algoritmer. Det giver en standardiseret måde at sammenligne effektiviteten af ​​forskellige algoritmer med hensyn til deres værst tænkelige ydeevne. Forståelse Stor O notation er afgørende for at analysere og designe effektive algoritmer.

I denne tutorial vil vi dække det grundlæggende i Stor O notation , dens betydning, og hvordan man analyserer kompleksiteten af ​​algoritmer ved hjælp af Store O .

Indholdsfortegnelse

• Hvad er Big-O-notation?
• Definition af Big-O notation:
• Hvorfor er Big O-notation vigtig?
• Egenskaber ved Big O-notation
• Almindelige Big-O-notationer
• Hvordan bestemmer man Big O-notation?
• Matematiske eksempler på Runtime Analysis
• Algoritmiske eksempler på runtime-analyse
• Algoritmeklasser med antal operationer og udførelsestid
• Sammenligning af Big O notation, Big Ω (Omega) notation og Big θ (Theta) notation
• Ofte stillede spørgsmål om Big O-notation

Hvad er Big-O-notation?

Big-O , almindeligvis omtalt som Rækkefølge af , er en måde at udtrykke det på øvre grænse af en algoritmes tidskompleksitet, da den analyserer værste tilfælde algoritmens situation. Det giver en Øverste grænse på den tid, en algoritme tager i forhold til størrelsen af ​​input. Det er betegnet som O(f(n)) , hvor f(n) er en funktion, der repræsenterer antallet af operationer (trin), som en algoritme udfører for at løse et problem af størrelse n .

Big-O notation bruges til at beskrive ydeevnen eller kompleksiteten af ​​en algoritme. Konkret beskriver den værste tilfælde med hensyn til tid eller rummets kompleksitet.

Vigtigt punkt:

• Stor O notation beskriver kun en funktions asymptotiske adfærd, ikke dens nøjagtige værdi.
• Det Stor O notation kan bruges til at sammenligne effektiviteten af ​​forskellige algoritmer eller datastrukturer.

Definition af Big-O notation:

Givet to funktioner f(n) og g(n) , det siger vi f(n) er O(g(n)) hvis der findes konstanter c> 0 og n ₀ >= 0 sådan f(n) <= c*g(n) for alle n>= n ₀ .

I enklere vendinger, f(n) er O(g(n)) hvis f(n) vokser ikke hurtigere end c*g(n) for alle n>= n₀hvor c og n₀er konstanter.

Hvorfor er Big O-notation vigtig?

Big O-notation er en matematisk notation, der bruges til at beskrive den værste tidskompleksitet eller effektiviteten af ​​en algoritme eller den værst tænkelige pladskompleksitet af en datastruktur. Det giver en måde at sammenligne ydeevnen af ​​forskellige algoritmer og datastrukturer og til at forudsige, hvordan de vil opføre sig, når inputstørrelsen øges.

Big O-notation er vigtig af flere grunde:

• Big O-notation er vigtig, fordi den hjælper med at analysere effektiviteten af ​​algoritmer.
• Det giver en måde at beskrive, hvordan køretid eller pladsbehov af en algoritme vokser, efterhånden som inputstørrelsen øges.
• Giver programmører mulighed for at sammenligne forskellige algoritmer og vælge den mest effektive til et specifikt problem.
• Hjælper med at forstå skalerbarheden af ​​algoritmer og forudsige, hvordan de vil fungere, efterhånden som inputstørrelsen vokser.
• Gør det muligt for udviklere at optimere kode og forbedre den samlede ydeevne.

Egenskaber ved Big O-notation:

Nedenfor er nogle vigtige egenskaber ved Big O-notation:

1. Refleksivitet:

For enhver funktion f(n), f(n) = O(f(n)).

Eksempel:

escape karakter java

f(n) = n², så f(n) = O(n²).

2. Transitivitet:

Hvis f(n) = O(g(n)) og g(n) = O(h(n)), så er f(n) = O(h(n)).

Eksempel:

f(n) = n³, g(n) = n², h(n) = n⁴. Så 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 funktioner f(n) og g(n), hvis f(n) = O(g(n)), så cf(n) = O(g(n)).

Eksempel:

java while loop

f(n) = n, g(n) = n². Så 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) = n², g(n) = n³, h(n) = n⁴. Så 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) = n², h(n) = n³, k(n) = n⁴. Så f(n) = O(g(n)) og h(n) = O(k(n)). Derfor f(n) * h(n) = O(g(n) * k(n)) = O(n⁵).

6. Sammensætningsregel:

Hvis f(n) = O(g(n)) og g(n) = O(h(n)), så er f(g(n)) = O(h(n)).

Eksempel:

f(n) = n², g(n) = n, h(n) = n³. Så f(n) = O(g(n)) og g(n) = O(h(n)). Derfor er f(g(n)) = O(h(n)) = O(n³).

Almindelige Big-O-notationer:

Big-O notation er en måde at måle kompleksiteten af ​​tid og rum i en algoritme. Den beskriver den øvre grænse for kompleksiteten i det værste tilfælde. Lad os se nærmere på de forskellige typer tidskompleksiteter:

1. Lineær tidskompleksitet: Stor O(n) kompleksitet

Lineær tidskompleksitet betyder, at køretiden for en algoritme vokser lineært med størrelsen af ​​input.

Overvej for eksempel en algoritme, der går gennem en matrix for at finde et bestemt element :

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 betyder, at køretiden for en algoritme er proportional med logaritmen af ​​inputstørrelsen.

For eksempel en binær søgealgoritme har en logaritmisk tidskompleksitet:

int binarySearch(int arr[], int l, int r, int x) {  if (r>= l) {int mid = l + (r - l) / 2;  hvis (arr[mid] == x) returner midt;  if (arr[mid]> x) returner binærsøgning(arr, l, mid - 1, x);  return binarySearch(arr, mid + 1, r, x);  } returnere -1; }>

3. Kvadratisk tidskompleksitet: Stor O(n²) Kompleksitet

Kvadratisk tidskompleksitet betyder, at køretiden for en algoritme er proportional med kvadratet på inputstørrelsen.

For eksempel en simpel boblesorteringsalgoritme har en kvadratisk tidskompleksitet:

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. Kubiktidskompleksitet: Stor O(n³) Kompleksitet

Kubisk tidskompleksitet betyder, at køretiden for en algoritme er proportional med kuben af ​​inputstørrelsen.

For eksempel en naiv matrix multiplikationsalgoritme har en kubisk tidskompleksitet:

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(n^k) Kompleksitet

Polynomisk tidskompleksitet refererer til tidskompleksiteten af ​​en algoritme, der kan udtrykkes som en polynomiel funktion af inputstørrelsen n . I Big O notation, siges en algoritme at have polynomisk tidskompleksitet, hvis dens tidskompleksitet er På ^k ) , hvor k er en konstant og repræsenterer graden af ​​polynomiet.

Algoritmer med polynomisk tidskompleksitet anses generelt for at være effektive, da køretiden vokser med en rimelig hastighed, når inputstørrelsen øges. Almindelige eksempler på algoritmer med polynomisk tidskompleksitet omfatter lineær tidskompleksitet O(n) , kvadratisk tidskompleksitet O(n ² ) , og kubiktidskompleksitet O(n ³ ) .

6. Eksponentiel tidskompleksitet: Big O(2ⁿ) Kompleksitet

Eksponentiel tidskompleksitet betyder, at køretiden for en algoritme fordobles med hver tilføjelse til inputdatasættet.

For eksempel problemet med generere alle delmængder af et sæt er af eksponentiel tidskompleksitet:

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

Faktoriel tidskompleksitet: Stor O(n!) kompleksitet

Faktoriel tidskompleksitet betyder, at køretiden for en algoritme vokser faktorielt med størrelsen af ​​inputtet. Dette ses ofte i algoritmer, der genererer alle permutationer af et sæt data.

Her er et eksempel på en faktoriel tidskompleksitetsalgoritme, som genererer alle permutationer af et array:

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 mest almindelige Big O-notationseksempler, ville vi have en graf som denne:

Hvordan bestemmer man Big O-notation?

Stor O notation er en matematisk notation, der bruges til at beskrive asymptotisk adfærd af en funktion, efterhånden som dens input bliver uendeligt stor. Det giver en måde at karakterisere effektiviteten af ​​algoritmer og datastrukturer.

forskel i python

Trin til at bestemme Big O-notation:

1. Identificer det dominerende udtryk:

• Undersøg funktionen og identificer udtrykket med den højeste vækstorden, når inputstørrelsen øges.
• Ignorer eventuelle konstante faktorer eller termer af lavere orden.

2. Bestem vækstrækkefølgen:

• Vækstrækkefølgen af ​​det dominerende udtryk bestemmer Big O-notationen.

3. Skriv Big O-notationen:

• Big O-notationen skrives som O(f(n)), hvor f(n) repræsenterer det dominerende led.
• For eksempel, hvis det dominerende led er n^2, vil Big O-notationen være O(n^2).

4. Forenkle notationen (valgfrit):

• I nogle tilfælde Big O branding n kan forenkles ved at fjerne konstante faktorer eller ved at bruge en mere kortfattet notation.
• For eksempel, O(2n) kan forenkles til På).

Eksempel:

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

1. Dominerende term: 3n³
2. Vækstorden: Kubisk (n³)
3. Big O-notation: O(n³)
4. Forenklet notation: O(n³)

Matematiske eksempler på runtime-analyse:

Nedenstående tabel illustrerer runtime-analysen af ​​forskellige rækkefølger af algoritmer, når inputstørrelsen (n) øges.

Algoritmiske eksempler på runtime-analyse:

Nedenstående tabel kategoriserer algoritmer baseret på deres runtime kompleksitet og giver eksempler for hver type.

Algoritmeklasser med antal operationer og udførelsestid:

Nedenfor er klasserne af algoritmer og deres eksekveringstider på en computer, der udfører 1 million operationer pr. sekund (1 sek = 10 ⁶ μsek = 10 ³ msek) :

Sammenligning af Big O notation, Big Ω (Omega) notation og Big θ (Theta) notation:

Nedenfor er en tabel, der sammenligner Big O notation, Ω (Omega) notation og θ (Theta) notation:

I hver notation:

• f(n) repræsenterer den funktion, der analyseres, typisk algoritmens tidskompleksitet.
• g(n) repræsenterer en specifik funktion, der afgrænser f(n) .
• C, C1, og C2 er konstanter.
• n ₀ er den mindste inputstørrelse, udover hvilken uligheden gælder.

Disse notationer bruges til at analysere algoritmer baseret på deres worst case (Big O) , bedste tilfælde (Ω) , og gennemsnit-case (θ) scenarier.

Ofte stillede spørgsmål om Big O-notation:

Spørgsmål 1. Hvad er Big O-notation?

Svar: Big O Notation er en matematisk notation, der bruges til at beskrive den øvre grænse for en algoritmes tidskompleksitet i forhold til, hvordan den vokser i forhold til størrelsen af ​​input.

Spørgsmål 2. Hvorfor er Big O-notation vigtig?

Svar: Det hjælper os med at analysere og sammenligne effektiviteten af ​​algoritmer ved at fokusere på det værst tænkelige scenarie og forstå, hvordan deres ydeevne skalerer med inputstørrelse.

Spørgsmål 3. Hvordan beregnes Big O Notation?

Svar: Big O Notation bestemmes ved at identificere den dominerende operation i en algoritme og udtrykke dens tidskompleksitet i form af n, hvor n repræsenterer inputstørrelsen.

Spørgsmål 4. Hvad betyder O(1) i Big O-notation?

Svar: O(1) angiver konstant tidskompleksitet, hvilket indikerer, at en algoritmes eksekveringstid ikke ændres uanset inputstørrelsen.

Spørgsmål 5. Hvad er betydningen af ​​forskellige Big O-kompleksiteter som O(log n) eller O(n^2)?

Svar: Forskellige kompleksiteter som O(log n) eller O(n^2) repræsenterer, hvordan en algoritmes ydeevne skaleres, når inputstørrelsen øges, hvilket giver indsigt i dens effektivitet og skalerbarhed.

Spørgsmål 6. Kan Big O-notation også anvendes på rumkompleksitet?

Svar: Ja, Big O Notation kan også bruges til at analysere og beskrive en algoritmes rumkompleksitet, hvilket angiver, hvor meget hukommelse den kræver i forhold til inputstørrelsen.

Relateret artikel:

• Eksempler på Big-O-analyse
• Design og analyse af algoritmer
• Typer af asymptotiske notationer i kompleksitetsanalyse af algoritmer
• Analyse af algoritmer | Big – Ω (Big- Omega) notation
• Analyse af algoritmer | lidt o og lidt omega notationer