Veliki O zapis je močno orodje, ki se uporablja v računalništvu za opisovanje časovne ali prostorske kompleksnosti algoritmov. Zagotavlja standardiziran način za primerjavo učinkovitosti različnih algoritmov v smislu njihovega najslabšega možnega delovanja. Razumevanje Veliki O zapis je bistvenega pomena za analizo in oblikovanje učinkovitih algoritmov.

V tej vadnici bomo obravnavali osnove Veliki O zapis , njegov pomen in kako analizirati kompleksnost uporabe algoritmov Veliki O .

Kazalo

• Kaj je zapis Big-O?
• Opredelitev zapisa Big-O:
• Zakaj je zapis Big O pomemben?
• Lastnosti zapisa velikega O
• Pogosti zapisi z velikim O
• Kako določiti zapis velikega O?
• Matematični primeri analize izvajalnega časa
• Algoritemski primeri analize izvajalnega časa
• Razredi algoritmov s številom operacij in časom izvajanja
• Primerjava zapisa velikega O, zapisa velikega Ω (omega) in zapisa velikega θ (theta)
• Pogosta vprašanja o zapisu Big O

Kaj je zapis Big-O?

Veliki-O , ki se običajno imenuje Vrstni red od , je način izražanja Zgornja meja časovne kompleksnosti algoritma, saj analizira v najslabšem primeru stanje algoritma. Zagotavlja Zgornja meja na čas, ki ga porabi algoritem glede na velikost vnosa. Označeno je kot O(f(n)) , kje f(n) je funkcija, ki predstavlja število operacij (korakov), ki jih algoritem izvede za rešitev problema velikosti n .

Zapis Big-O se uporablja za opis zmogljivosti ali kompleksnosti algoritma. Natančneje, opisuje najslabši možni scenarij v smislu čas oz kompleksnost prostora.

Pomembna točka:

• Veliki O zapis opisuje le asimptotično obnašanje funkcije, ne pa njene natančne vrednosti.
• The Veliki O zapis se lahko uporablja za primerjavo učinkovitosti različnih algoritmov ali podatkovnih struktur.

Opredelitev zapisa Big-O:

Glede na dve funkciji f(n) in g(n) , to pravimo f(n) je O(g(n)) če obstajajo konstante c> 0 in n ₀ >= 0 tako, da f(n) <= c*g(n) za vse n>= n ₀ .

Preprosteje rečeno, f(n) je O(g(n)) če f(n) ne raste hitreje kot c*g(n) za vse n>= n₀kjer sta c in n₀so konstante.

prekiniti javo

Zakaj je zapis Big O pomemben?

Zapis Big O je matematični zapis, ki se uporablja za opis najslabše možne časovne kompleksnosti ali učinkovitosti algoritma ali najslabše možne prostorske kompleksnosti podatkovne strukture. Zagotavlja način za primerjavo delovanja različnih algoritmov in podatkovnih struktur ter za predvidevanje, kako se bodo obnašali, ko se velikost vnosa poveča.

Zapis z velikim O je pomemben iz več razlogov:

• Zapis Big O je pomemben, ker pomaga analizirati učinkovitost algoritmov.
• Ponuja način za opis, kako čas izvajanja oz prostorske zahteve algoritma rastejo z večanjem velikosti vnosa.
• Programerjem omogoča primerjavo različnih algoritmov in izbiro najučinkovitejšega za določen problem.
• Pomaga pri razumevanju razširljivosti algoritmov in predvidevanju, kako bodo delovali, ko bo velikost vnosa naraščala.
• Omogoča razvijalcem, da optimizirajo kodo in izboljšajo splošno zmogljivost.

Lastnosti zapisa Big O:

Spodaj je nekaj pomembnih lastnosti zapisa Big O:

1. Refleksivnost:

Za katero koli funkcijo f(n) je f(n) = O(f(n)).

primer:

f(n) = n², potem je f(n) = O(n²).

2. Prehodnost:

Če je f(n) = O(g(n)) in g(n) = O(h(n)), potem je f(n) = O(h(n)).

primer:

f(n) = n³, g(n) = n², h(n) = n⁴. Potem je f(n) = O(g(n)) in g(n) = O(h(n)). Zato je f(n) = O(h(n)).

3. Konstantni faktor:

Za katero koli konstanto c> 0 in funkciji f(n) in g(n), če je f(n) = O(g(n)), potem je cf(n) = O(g(n)).

primer:

f(n) = n, g(n) = n². Potem je f(n) = O(g(n)). Zato je 2f(n) = O(g(n)).

4. Pravilo vsote:

Če je f(n) = O(g(n)) in h(n) = O(g(n)), potem je f(n) + h(n) = O(g(n)).

primer:

f(n) = n², g(n) = n³, h(n) = n⁴. Potem je f(n) = O(g(n)) in h(n) = O(g(n)). Zato je f(n) + h(n) = O(g(n)).

5. Pravilo izdelka:

Če je f(n) = O(g(n)) in h(n) = O(k(n)), potem je f(n) * h(n) = O(g(n) * k(n)) .

primer:

f(n) = n, g(n) = n², h(n) = n³, k(n) = n⁴. Potem je f(n) = O(g(n)) in h(n) = O(k(n)). Zato je f(n) * h(n) = O(g(n) * k(n)) = O(n⁵).

6. Pravilo sestave:

Če je f(n) = O(g(n)) in g(n) = O(h(n)), potem je f(g(n)) = O(h(n)).

primer:

f(n) = n², g(n) = n, h(n) = n³. Potem je f(n) = O(g(n)) in g(n) = O(h(n)). Zato je f(g(n)) = O(h(n)) = O(n³).

Pogoste oznake z velikimi črkami:

Zapis Big-O je način za merjenje časovne in prostorske kompleksnosti algoritma. Opisuje zgornjo mejo kompleksnosti v najslabšem primeru. Oglejmo si različne vrste časovne kompleksnosti:

1. Linearna časovna zapletenost: velika O(n) zapletenost

Linearna časovna kompleksnost pomeni, da čas delovanja algoritma raste linearno z velikostjo vnosa.

Na primer, razmislite o algoritmu, ki prečka matriko, da najde določen 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. Logaritemska časovna kompleksnost: velika O(log n) kompleksnost

Logaritemska časovna kompleksnost pomeni, da je čas delovanja algoritma sorazmeren z logaritmom velikosti vnosa.

Na primer, a binarni iskalni algoritem ima logaritemsko časovno kompleksnost:

int binarySearch(int arr[], int l, int r, int x) {  if (r>= l) { int mid = l + (r - l) / 2;  if (arr[mid] == x) vrni sredino;  if (arr[mid]> x) vrni binarySearch(arr, l, mid - 1, x);  return binarySearch(arr, mid + 1, r, x);  } vrni -1; }>

3. Kvadratna časovna kompleksnost: Big O(n²) Kompleksnost

Kvadratna časovna kompleksnost pomeni, da je čas delovanja algoritma sorazmeren s kvadratom velikosti vnosa.

Na primer, preprosto algoritem za razvrščanje mehurčkov ima kvadratno časovno kompleksnost:

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]) { zamenjaj(&arr[j], &arr[j + 1]);  } } } }>

4. Kompleksnost kubičnega časa: Big O(n³) Kompleksnost

Kubična časovna kompleksnost pomeni, da je čas delovanja algoritma sorazmeren s kocko velikosti vnosa.

Na primer, naiven algoritem množenja matrik ima kompleksnost kubičnega časa:

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. Polinomska časovna kompleksnost: Big O(n^k) Kompleksnost

Polinomska časovna kompleksnost se nanaša na časovno kompleksnost algoritma, ki se lahko izrazi kot polinomska funkcija velikosti vnosa n . V Big O zapisu, pravimo, da ima algoritem polinomsko časovno kompleksnost, če je njegova časovna kompleksnost O(n ^k ) , kje k je konstanta in predstavlja stopnjo polinoma.

Algoritmi s polinomsko časovno kompleksnostjo na splošno veljajo za učinkovite, saj čas delovanja raste z razumno hitrostjo, ko se povečuje velikost vnosa. Pogosti primeri algoritmov s polinomsko časovno kompleksnostjo vključujejo linearna časovna kompleksnost O(n) , kvadratna časovna kompleksnost O(n ² ) , in kubična časovna kompleksnost O(n ³ ) .

6. Eksponentna časovna kompleksnost: Big O(2ⁿ) Kompleksnost

Eksponentna časovna kompleksnost pomeni, da se čas delovanja algoritma podvoji z vsakim dodatkom k vhodnemu nizu podatkov.

Na primer, problem generiranje vseh podmnožic množice je eksponentne časovne kompleksnosti:

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

Faktorska časovna zapletenost: velika O(n!) zapletenost

Faktorska časovna kompleksnost pomeni, da čas delovanja algoritma raste faktorsko z velikostjo vhoda. To pogosto vidimo v algoritmih, ki generirajo vse permutacije nabora podatkov.

Tukaj je primer algoritma faktorske časovne kompleksnosti, ki generira vse permutacije matrike:

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

Če narišemo najpogostejše primere zapisa velikega O, bi imeli graf, kot je ta:

Kako določiti zapis velikega O?

Veliki O zapis je matematični zapis, ki se uporablja za opis asimptotično vedenje funkcije, ko njen vhod neskončno raste. Ponuja način za karakterizacijo učinkovitosti algoritmov in podatkovnih struktur.

Koraki za določitev zapisa velikega O:

1. Določite prevladujoč izraz:

• Preglejte funkcijo in identificirajte izraz z najvišjim vrstnim redom rasti, ko se velikost vnosa povečuje.
• Zanemarjajte vse konstantne faktorje ali člene nižjega reda.

2. Določite vrstni red rasti:

char v celo število java

• Vrstni red rasti prevladujočega člena določa zapis velikega O.

3. Zapišite oznako Big O:

• Zapis Big O je zapisan kot O(f(n)), kjer f(n) predstavlja prevladujoč izraz.
• Na primer, če je prevladujoči člen n^2, bi bil zapis Big O O(n^2).

4. Poenostavite zapis (neobvezno):

• V nekaterih primerih je Blagovna znamka Big O n lahko poenostavimo z odstranitvijo stalnih faktorjev ali z uporabo bolj jedrnatega zapisa.
• Na primer, O(2n) se lahko poenostavi na O(n).

primer:

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

1. Dominantni izraz: 3n³
2. Vrstni red rasti: kubični (n³)
3. Zapis velike O: O(n³)
4. Poenostavljen zapis: O(n³)

Matematični primeri analize izvajalnega časa:

Spodnja tabela ponazarja analizo časa izvajanja različnih vrstnih redov algoritmov, ko se velikost vnosa (n) povečuje.

Algoritemski primeri analize izvajalnega časa:

Spodnja tabela kategorizira algoritme glede na njihovo izvajalno kompleksnost in nudi primere za vsako vrsto.

Razredi algoritmov s številom operacij in časom izvajanja:

Spodaj so razredi algoritmov in njihovi časi izvajanja na računalniku, ki se izvaja 1 milijon operacij na sekundo (1 s = 10 ⁶ μsek = 10 ³ msec) :

Primerjava zapisa velikega O, zapisa velikega Ω (omega) in zapisa velikega θ (theta):

Spodaj je tabela primerjave zapisa Big O, zapisa Ω (Omega) in zapisa θ (Theta):

V vsaki notaciji:

• f(n) predstavlja funkcijo, ki se analizira, običajno časovno kompleksnost algoritma.
• g(n) predstavlja specifično funkcijo, ki omejuje f(n) .
• C, C1, in C2 so konstante.
• n ₀ ​ je najmanjša velikost vnosa, nad katero velja neenakost.

Ti zapisi se uporabljajo za analizo algoritmov, ki temeljijo na njihovih v najslabšem primeru (veliki O) , najboljši primer (Ω) , in povprečni primer (θ) scenariji.

Pogosta vprašanja o zapisu velikega O:

Vprašanje 1. Kaj je zapis velikega O?

odgovor: Zapis Big O je matematični zapis, ki se uporablja za opis zgornje meje časovne kompleksnosti algoritma v smislu tega, kako raste glede na velikost vnosa.

Vprašanje 2. Zakaj je zapis Big O pomemben?

odgovor: Pomaga nam analizirati in primerjati učinkovitost algoritmov tako, da se osredotoči na najslabši možni scenarij in razume, kako se njihova zmogljivost spreminja z velikostjo vnosa.

Vprašanje 3. Kako se izračuna oznaka Big O?

odgovor: Zapis Big O se določi z identifikacijo prevladujoče operacije v algoritmu in izražanjem njegove časovne kompleksnosti v smislu n, kjer n predstavlja velikost vhoda.

Vprašanje 4. Kaj pomeni O(1) v zapisu Big O?

odgovor: O(1) označuje konstantno časovno kompleksnost, kar pomeni, da se čas izvajanja algoritma ne spreminja ne glede na velikost vnosa.

Vprašanje 5. Kakšen je pomen različnih zapletenosti velikega O, kot je O(log n) ali O(n^2)?

odgovor: Različne zapletenosti, kot sta O(log n) ali O(n^2), predstavljajo, kako se zmogljivost algoritma spreminja, ko se poveča velikost vnosa, kar zagotavlja vpogled v njegovo učinkovitost in razširljivost.

Vprašanje 6. Ali se lahko zapis Big O uporabi tudi za kompleksnost prostora?

odgovor: Da, zapis Big O se lahko uporablja tudi za analizo in opis kompleksnosti prostora algoritma, ki kaže, koliko pomnilnika potrebuje glede na velikost vnosa.

Sorodni članek:

• Primeri analize Big-O
• Oblikovanje in analiza algoritmov
• Vrste asimptotičnih zapisov v analizi kompleksnosti algoritmov
• Analiza algoritmov | Big – Ω (Big- Omega) zapis
• Analiza algoritmov | malo o in malo omega