Veľký O zápis je výkonný nástroj používaný v informatike na opis časovej alebo priestorovej zložitosti algoritmov. Poskytuje štandardizovaný spôsob porovnávania účinnosti rôznych algoritmov z hľadiska ich výkonu v najhoršom prípade. Porozumenie Veľký O zápis je nevyhnutný pre analýzu a navrhovanie efektívnych algoritmov.

V tomto návode sa budeme zaoberať základmi Veľký O zápis , jej význam a ako analyzovať zložitosť použitých algoritmov Veľký O .

Obsah

• Čo je to Big-O Notation?
• Definícia Big-O notácie:
• Prečo je zápis veľkého O dôležitý?
• Vlastnosti veľkého O zápisu
• Bežné Big-O notácie
• Ako určiť veľký O zápis?
• Matematické príklady runtime analýzy
• Algoritmické príklady runtime analýzy
• Triedy algoritmov s počtom operácií a časom vykonania
• Porovnanie veľkého O, Big Ω (Omega) notácie a Big θ (Theta) notácie
• Často kladené otázky o zápise veľkého O

Čo je to Big-O Notation?

Big-O , bežne označovaný ako Objednávka , je spôsob vyjadrenia Horná hranica časovej zložitosti algoritmu, pretože analyzuje v najhoršom prípade situáciu algoritmu. Poskytuje Horná hranica na čase, ktorý algoritmus potrebuje z hľadiska veľkosti vstupu. Označuje sa ako O(f(n)) , kde f(n) je funkcia, ktorá predstavuje počet operácií (krokov), ktoré algoritmus vykoná, aby vyriešil problém veľkosti n .

Big-O zápis sa používa na opis výkonu alebo zložitosti algoritmu. Konkrétne popisuje najhorší prípad v zmysle čas alebo priestorovú zložitosť.

Dôležitý bod:

• Veľký O zápis opisuje iba asymptotické správanie funkcie, nie jej presnú hodnotu.
• The Veľký O zápis možno použiť na porovnanie účinnosti rôznych algoritmov alebo dátových štruktúr.

Definícia Big-O notácie:

Dané dve funkcie f(n) a g(n) , hovoríme to f(n) je O(g(n)) ak existujú konštanty c> 0 a n ₀ >= 0 taký, že f(n) <= c*g(n) pre všetkých n>= n ₀ .

Jednoduchšie povedané, f(n) je O(g(n)) ak f(n) nerastie rýchlejšie ako c*g(n) pre všetky n>= n₀kde c a n₀sú konštanty.

Prečo je zápis veľkého O dôležitý?

Veľký O zápis je matematický zápis používaný na opísanie časovej zložitosti alebo účinnosti algoritmu v najhoršom prípade alebo priestorovej zložitosti v najhoršom prípade dátovej štruktúry. Poskytuje spôsob, ako porovnať výkon rôznych algoritmov a dátových štruktúr a predpovedať, ako sa budú správať, keď sa veľkosť vstupu zvýši.

Veľké O je dôležité z niekoľkých dôvodov:

• Big O Notation je dôležitý, pretože pomáha analyzovať efektivitu algoritmov.
• Poskytuje spôsob, ako opísať, ako beh programu alebo priestorové požiadavky algoritmu rastie so zvyšujúcou sa veľkosťou vstupu.
• Umožňuje programátorom porovnávať rôzne algoritmy a vybrať ten najefektívnejší pre konkrétny problém.
• Pomáha pochopiť škálovateľnosť algoritmov a predpovedať, ako budú fungovať s rastúcou veľkosťou vstupu.
• Umožňuje vývojárom optimalizovať kód a zlepšiť celkový výkon.

Vlastnosti zápisu veľkého O:

Nižšie sú uvedené niektoré dôležité vlastnosti notácie Big O:

1. Reflexivita:

Pre ľubovoľnú funkciu f(n) platí f(n) = O(f(n)).

Príklad:

f(n) = n²potom f(n) = O(n²).

2. Prechodnosť:

Ak f(n) = O(g(n)) a g(n) = O(h(n)), potom f(n) = O(h(n)).

Príklad:

f(n) = n³, g(n) = n², h(n) = n⁴. Potom f(n) = O(g(n)) a g(n) = O(h(n)). Preto f(n) = O(h(n)).

matematická trieda java

3. Konštantný faktor:

Pre ľubovoľnú konštantu c> 0 a funkcie f(n) a g(n) platí, že ak f(n) = O(g(n)), potom cf(n) = O(g(n)).

Príklad:

f(n) = n, g(n) = n². Potom f(n) = O(g(n)). Preto 2f(n) = O(g(n)).

4. Pravidlo súčtu:

Ak f(n) = O(g(n)) a h(n) = O(g(n)), potom f(n) + h(n) = O(g(n)).

Príklad:

f(n) = n², g(n) = n³, h(n) = n⁴. Potom f(n) = O(g(n)) a h(n) = O(g(n)). Preto f(n) + h(n) = O(g(n)).

5. Produktové pravidlo:

Ak f(n) = O(g(n)) a h(n) = O(k(n)), potom f(n) * h(n) = O(g(n) * k(n)) .

Príklad:

f(n) = n, g(n) = n², h(n) = n³, k(n) = n⁴. Potom f(n) = O(g(n)) a h(n) = O(k(n)). Preto f(n) * h(n) = O(g(n) * k(n)) = O(n⁵).

6. Pravidlo zloženia:

Ak f(n) = O(g(n)) a g(n) = O(h(n)), potom f(g(n)) = O(h(n)).

Príklad:

f(n) = n²g(n) = n, h(n) = n³. Potom f(n) = O(g(n)) a g(n) = O(h(n)). Preto f(g(n)) = O(h(n)) = O(n³).

Bežné Big-O notácie:

Big-O zápis je spôsob merania časovej a priestorovej zložitosti algoritmu. Popisuje hornú hranicu zložitosti v najhoršom prípade. Pozrime sa na rôzne typy časovej zložitosti:

1. Lineárna časová zložitosť: Veľká O(n) zložitosť

Lineárna časová zložitosť znamená, že čas chodu algoritmu rastie lineárne s veľkosťou vstupu.

Zvážte napríklad algoritmus, ktorý prechádza cez pole, aby našiel konkrétny prvok :

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

2. Logaritmická časová zložitosť: Veľká O (log n) zložitosť

Logaritmická časová zložitosť znamená, že čas chodu algoritmu je úmerný logaritmu veľkosti vstupu.

Napríklad a binárny vyhľadávací algoritmus má logaritmickú časovú zložitosť:

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

3. Kvadratická časová zložitosť: Veľký O(n²) Zložitosť

Kvadratická časová zložitosť znamená, že čas chodu algoritmu je úmerný druhej mocnine veľkosti vstupu.

Napríklad jednoduchý algoritmus triedenia bublín má kvadratickú časovú zložitosť:

skener java

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. Kubická časová zložitosť: Veľké O (č³) Zložitosť

Kubická časová zložitosť znamená, že čas chodu algoritmu je úmerný kocke vstupnej veľkosti.

Napríklad naivný algoritmus násobenia matice má kubickú časovú zložitosť:

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. Polynomiálna časová zložitosť: Veľký O(n^k) Zložitosť

Polynomiálna časová zložitosť sa týka časovej zložitosti algoritmu, ktorú možno vyjadriť ako polynomickú funkciu veľkosti vstupu. n . Vo Veľkom O zápisu sa hovorí, že algoritmus má polynomiálnu časovú zložitosť, ak je jeho časová zložitosť O(n ^k ) , kde k je konštanta a predstavuje stupeň polynómu.

Algoritmy s polynomiálnou časovou zložitosťou sa vo všeobecnosti považujú za efektívne, pretože prevádzkový čas rastie primeranou rýchlosťou so zvyšujúcou sa veľkosťou vstupu. Bežné príklady algoritmov s polynomiálnou časovou zložitosťou zahŕňajú lineárna časová zložitosť O(n) , kvadratická časová zložitosť O(n ² ) , a kubická časová zložitosť O(n ³ ) .

6. Exponenciálna časová zložitosť: Veľký O(2ⁿ) Zložitosť

Exponenciálna časová zložitosť znamená, že čas chodu algoritmu sa zdvojnásobuje s každým pridaním do súboru vstupných údajov.

Napríklad problém generovanie všetkých podmnožín množiny má exponenciálnu časovú zložitosť:

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

Faktorová časová zložitosť: Veľká O(n!) zložitosť

Faktorová časová zložitosť znamená, že čas chodu algoritmu rastie faktoriálne s veľkosťou vstupu. Toto je často vidieť v algoritmoch, ktoré generujú všetky permutácie množiny údajov.

Tu je príklad algoritmu faktoriálnej časovej zložitosti, ktorý generuje všetky permutácie poľa:

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

Ak nakreslíme najbežnejšie príklady zápisu Big O, mali by sme takýto graf:

Ako určiť veľký O zápis?

Veľký O zápis je matematický zápis používaný na opis asymptotické správanie funkcie, pretože jej vstup rastie nekonečne veľký. Poskytuje spôsob, ako charakterizovať účinnosť algoritmov a dátových štruktúr.

Kroky na určenie veľkého O zápisu:

1. Identifikujte dominantný výraz:

• Preskúmajte funkciu a identifikujte výraz s najvyšším rádom rastu, keď sa veľkosť vstupu zvyšuje.
• Ignorujte akékoľvek konštantné faktory alebo termíny nižšieho rádu.

2. Určite poradie rastu:

• Poradie rastu dominantného člena určuje zápis veľkého O.

3. Napíšte veľké O:

• Veľký O zápis sa píše ako O(f(n)), kde f(n) predstavuje dominantný člen.
• Napríklad, ak je dominantný člen n^2, zápis veľkého O bude O(n^2).

4. Zjednodušte zápis (voliteľné):

• V niektorých prípadoch je Značka Big O n možno zjednodušiť odstránením konštantných faktorov alebo použitím stručnejšieho zápisu.
• napr. O(2n) možno zjednodušiť na O(n).

Príklad:

panel nástrojov rýchleho prístupu word

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

1. Dominantný termín: 3n³
2. Poradie rastu: kubický (n³)
3. Veľký O zápis: O(n³)
4. Zjednodušená notácia: O(č³)

Matematické príklady analýzy spustenia:

Nižšie uvedená tabuľka ilustruje runtime analýzu rôznych rádov algoritmov so zvyšujúcou sa veľkosťou vstupu (n).

Algoritmické príklady analýzy spustenia:

Nižšie uvedená tabuľka kategorizuje algoritmy na základe ich zložitosti za behu a poskytuje príklady pre každý typ.

Triedy algoritmov s počtom operácií a časom vykonania:

Nižšie sú uvedené triedy algoritmov a časy ich vykonávania na počítači 1 milión operácií za sekundu (1 s = 10 ⁶ μs = 10 ³ ms) :

Porovnanie veľkého O, Big Ω (Omega) notácie a Big θ (Theta) notácie:

Nižšie je uvedená tabuľka porovnávajúca notáciu Big O, notáciu Ω (Omega) a notáciu θ (Theta):

V každom zápise:

• f(n) predstavuje analyzovanú funkciu, zvyčajne časovú zložitosť algoritmu.
• g(n) predstavuje špecifickú funkciu, ktorá ohraničuje f(n) .
• C, C1, a C2 sú konštanty.
• n ₀ je minimálna vstupná veľkosť, za ktorou nerovnosť platí.

Tieto zápisy sa používajú na analýzu algoritmov založených na nich najhorší prípad (veľké O) , najlepší prípad (Ω) , a priemerný prípad (θ) scenárov.

Často kladené otázky o zápise veľkého O:

Otázka 1. Čo je to veľký O zápis?

odpoveď: Big O Notation je matematický zápis používaný na opis hornej hranice časovej zložitosti algoritmu z hľadiska toho, ako rastie vzhľadom na veľkosť vstupu.

Otázka 2. Prečo je veľký zápis písmena O dôležitý?

odpoveď: Pomáha nám analyzovať a porovnávať efektivitu algoritmov tým, že sa zameriame na najhorší scenár a pochopíme, ako sa ich výkon mení s veľkosťou vstupu.

Otázka 3. Ako sa vypočítava veľké O?

odpoveď: Veľký O zápis je určený identifikáciou dominantnej operácie v algoritme a vyjadrením jej časovej zložitosti v zmysle n, kde n predstavuje vstupnú veľkosť.

Otázka 4. Čo znamená O(1) vo veľkom O?

odpoveď: O(1) znamená konštantnú časovú zložitosť, čo naznačuje, že čas vykonania algoritmu sa nemení bez ohľadu na veľkosť vstupu.

Otázka 5. Aký je význam rôznych zložitostí veľkého O ako O(log n) alebo O(n^2)?

odpoveď: Rôzne zložitosti ako O(log n) alebo O(n^2) predstavujú, ako sa výkon algoritmu škáluje so zvyšujúcou sa veľkosťou vstupu, čo poskytuje prehľad o jeho efektívnosti a škálovateľnosti.

Otázka 6. Dá sa Big O Notation aplikovať aj na priestorovú zložitosť?

odpoveď: Áno, Big O Notation je možné použiť aj na analýzu a popis priestorovej zložitosti algoritmu, čo naznačuje, koľko pamäte vyžaduje v pomere k veľkosti vstupu.

Súvisiaci článok:

• Príklady Big-O analýzy
• Návrh a analýza algoritmov
• Typy asymptotických zápisov v analýze zložitosti algoritmov
• Analýza algoritmov | Veľký – Ω (veľký – Omega) zápis
• Analýza algoritmov | malé o a málo omega notácie