Velký O zápis je mocný nástroj používaný v informatice k popisu časové nebo prostorové složitosti algoritmů. Poskytuje standardizovaný způsob, jak porovnávat účinnost různých algoritmů z hlediska jejich výkonu v nejhorším případě. Porozumění Velký O zápis je nezbytný pro analýzu a navrhování účinných algoritmů.

V tomto tutoriálu probereme základy Velký O zápis , jeho význam a jak analyzovat složitost použitých algoritmů Velký O .

Obsah

• Co je to Big-O Notation?
• Definice Big-O notace:
• Proč je zápis velkého O důležitý?
• Vlastnosti velkého O zápisu
• Běžné Big-O notace
• Jak určit velký O zápis?
• Matematické příklady runtime analýzy
• Algoritmické příklady runtime analýzy
• Třídy algoritmů s počtem operací a dobou provedení
• Porovnání notace velkého O, notace velkého Ω (Omega) a notace velkého θ (theta)
• Často kladené otázky o velkém O notaci

Co je to Big-O Notation?

Big-O , běžně označované jako Řád , je způsob, jak vyjádřit horní hranice časové složitosti algoritmu, protože analyzuje nejhorší případ situace algoritmu. Poskytuje horní limit na čase, který algoritmus zabere z hlediska velikosti vstupu. Označuje se jako O(f(n)) , kde f(n) je funkce, která představuje počet operací (kroků), které algoritmus provede, aby vyřešil problém velikosti n .

Big-O zápis se používá k popisu výkonu nebo složitosti algoritmu. Konkrétně popisuje nejhorší možný scénář ve smyslu čas nebo prostorová složitost.

Důležitý bod:

• Velký O zápis popisuje pouze asymptotické chování funkce, nikoli její přesnou hodnotu.
• The Velký O zápis lze použít k porovnání účinnosti různých algoritmů nebo datových struktur.

Definice Big-O notace:

Jsou dány dvě funkce f(n) a g(n) , říkáme to f(n) je O(g(n)) pokud existují konstanty c> 0 a n ₀ >= 0 takové, že f(n) <= c*g(n) pro všechny n>= n ₀ .

Jednodušeji řečeno, f(n) je O(g(n)) -li f(n) neroste rychleji než c*g(n) pro všechna n>= n₀kde c a n₀jsou konstanty.

Proč je zápis velkého O důležitý?

Velký O zápis je matematický zápis používaný k popisu nejhorší časové složitosti nebo účinnosti algoritmu nebo nejhorší případové prostorové složitosti datové struktury. Poskytuje způsob, jak porovnat výkon různých algoritmů a datových struktur a předpovědět, jak se budou chovat, když se zvětší velikost vstupu.

Velké O je důležité z několika důvodů:

• Big O Notation je důležitý, protože pomáhá analyzovat efektivitu algoritmů.
• Poskytuje způsob, jak popsat, jak runtime nebo prostorové nároky algoritmu roste s rostoucí velikostí vstupu.
• Umožňuje programátorům porovnat různé algoritmy a vybrat ten nejúčinnější pro konkrétní problém.
• Pomáhá pochopit škálovatelnost algoritmů a předvídat, jak budou fungovat s rostoucí velikostí vstupu.
• Umožňuje vývojářům optimalizovat kód a zlepšit celkový výkon.

Vlastnosti zápisu velkého O:

Níže jsou uvedeny některé důležité vlastnosti velkého O notace:

1. Reflexivita:

Pro libovolnou funkci f(n) platí f(n) = O(f(n)).

Příklad:

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

2. Přechodnost:

Jestliže f(n) = O(g(n)) a g(n) = O(h(n)), pak f(n) = O(h(n)).

Příklad:

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

3. Konstantní faktor:

Pro libovolnou konstantu c> 0 a funkce f(n) a g(n) platí, že pokud f(n) = O(g(n)), pak cf(n) = O(g(n)).

Příklad:

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

4. Pravidlo součtu:

Jestliže f(n) = O(g(n)) a h(n) = O(g(n)), pak f(n) + h(n) = O(g(n)).

Příklad:

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

5. Produktové pravidlo:

Pokud f(n) = O(g(n)) a h(n) = O(k(n)), pak f(n) * h(n) = O(g(n) * k(n)) .

Pří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)). Proto f(n) * h(n) = O(g(n) * k(n)) = O(n⁵).

6. Pravidlo složení:

Jestliže f(n) = O(g(n)) a g(n) = O(h(n)), pak f(g(n)) = O(h(n)).

Příklad:

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

Běžné Big-O notace:

Big-O notace je způsob, jak měřit časovou a prostorovou složitost algoritmu. Popisuje horní hranici složitosti v nejhorším případě. Podívejme se na různé typy časové složitosti:

1. Lineární časová složitost: Velká O(n) složitost

Lineární časová složitost znamená, že doba běhu algoritmu roste lineárně s velikostí vstupu.

Zvažte například algoritmus, který projde polem a najde konkrétní prvek :

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á složitost: Velká O(log n) složitost

Logaritmická časová složitost znamená, že doba běhu algoritmu je úměrná logaritmu velikosti vstupu.

Například a binární vyhledávací algoritmus má logaritmickou časovou složitost:

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

3. Kvadratická časová složitost: Velký O(č²) Složitost

Kvadratická časová složitost znamená, že doba běhu algoritmu je úměrná druhé mocnině vstupní velikosti.

Například jednoduchý algoritmus pro třídění bublin má kvadratickou časovou složitost:

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á složitost: Velké O(č³) Složitost

Krychlová časová složitost znamená, že doba běhu algoritmu je úměrná krychli vstupní velikosti.

Například naivka maticový násobící algoritmus má kubickou časovou složitost:

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ální časová složitost: Velký O(n^k) Složitost

Polynomiální časová složitost odkazuje na časovou složitost algoritmu, kterou lze vyjádřit jako polynomiální funkci vstupní velikosti. n . Ve Velké Ó zápisu se říká, že algoritmus má polynomiální časovou složitost, pokud je jeho časová složitost Na ^k ) , kde k je konstanta a představuje stupeň polynomu.

Algoritmy s polynomiální časovou složitostí jsou obecně považovány za efektivní, protože doba běhu roste přiměřenou rychlostí s rostoucí velikostí vstupu. Mezi běžné příklady algoritmů s polynomiální časovou složitostí patří lineární časová složitost O(n) , kvadratická časová složitost O(n ² ) , a kubická časová složitost O(n ³ ) .

6. Exponenciální časová složitost: Velký O(2ⁿ) Složitost

Exponenciální časová složitost znamená, že doba běhu algoritmu se zdvojnásobuje s každým přidáním do sady vstupních dat.

Například problém generování všech podmnožin množiny má exponenciální časovou složitost:

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á složitost: Velká O(n!) Složitost

Faktorová časová složitost znamená, že doba běhu algoritmu roste faktoriálně s velikostí vstupu. To je často vidět v algoritmech, které generují všechny permutace sady dat.

Zde je příklad algoritmu faktoriálové časové složitosti, který generuje všechny permutace pole:

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

Pokud vykreslíme nejběžnější příklady zápisu Big O, měli bychom graf takto:

Jak určit velký O zápis?

Velký O zápis je matematický zápis používaný k popisu asymptotické chování funkce, když její vstup nekonečně roste. Poskytuje způsob, jak charakterizovat efektivitu algoritmů a datových struktur.

pole řetězců

Kroky k určení velkého O zápisu:

1. Určete dominantní výraz:

• Prozkoumejte funkci a identifikujte termín s nejvyšším řádem růstu, jak se zvětšuje vstupní velikost.
• Ignorujte jakékoli konstantní faktory nebo termíny nižšího řádu.

2. Určete pořadí růstu:

• Pořadí růstu dominantního členu určuje zápis velkého O.

3. Napište velké O:

• Velký O zápis se zapisuje jako O(f(n)), kde f(n) představuje dominantní člen.
• Pokud je například dominantní člen n^2, zápis velkého O bude O(n^2).

4. Zjednodušte zápis (volitelné):

• V některých případech je Značka Big O n lze zjednodušit odstraněním konstantních faktorů nebo použitím stručnějšího zápisu.
• Například, O(2n) lze zjednodušit na Na).

Příklad:

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

1. Dominantní termín: 3n³
2. Pořadí růstu: krychlový (n³)
3. Velký O zápis: O(n³)
4. Zjednodušený zápis: O(n³)

Matematické příklady analýzy za běhu:

Níže uvedená tabulka ilustruje runtime analýzu různých řádů algoritmů se zvyšující se velikostí vstupu (n).

Algoritmické příklady analýzy za běhu:

Níže uvedená tabulka kategorizuje algoritmy na základě jejich složitosti za běhu a poskytuje příklady pro každý typ.

Třídy algoritmů s počtem operací a dobou provedení:

Níže jsou uvedeny třídy algoritmů a jejich doby provádění na spuštěném počítači 1 milion operací za sekundu (1 s = 10 ⁶ μs = 10 ³ ms) :

Porovnání notace velkého O, notace velkého Ω (Omega) a notace velkého θ (theta):

Níže je tabulka srovnávající notaci Big O, notaci Ω (Omega) a notaci θ (Theta):

V každém zápisu:

• f(n) představuje analyzovanou funkci, obvykle časovou složitost algoritmu.
• g(n) představuje specifickou funkci, která omezuje f(n) .
• C, C1, a C2 jsou konstanty.
• n ₀ je minimální vstupní velikost, za kterou platí nerovnost.

Tyto zápisy se používají k analýze algoritmů na jejich základě nejhorší případ (velké O) , nejlepší případ (Ω) , a průměrný případ (θ) scénáře.

Často kladené otázky týkající se notace velkého O:

Otázka 1. Co je velký O zápis?

Odpovědět: Big O Notation je matematický zápis používaný k popisu horní hranice časové složitosti algoritmu z hlediska toho, jak roste vzhledem k velikosti vstupu.

Otázka 2. Proč je notace velkého O důležitá?

Odpovědět: Pomáhá nám analyzovat a porovnávat efektivitu algoritmů tím, že se zaměříme na nejhorší scénář a pochopíme, jak se jejich výkon mění s velikostí vstupu.

Otázka 3. Jak se počítá notace Big O?

Odpovědět: Zápis velkého O je určen identifikací dominantní operace v algoritmu a vyjádřením její časové složitosti pomocí n, kde n představuje vstupní velikost.

Otázka 4. Co znamená O(1) ve velkém O?

Odpovědět: O(1) znamená konstantní časovou složitost, což znamená, že doba provádění algoritmu se nemění bez ohledu na velikost vstupu.

Otázka 5. Jaký je význam různých složitostí velkého O, jako je O(log n) nebo O(n^2)?

Odpovědět: Různé složitosti jako O(log n) nebo O(n^2) představují, jak se výkon algoritmu škáluje s rostoucí velikostí vstupu, což poskytuje přehled o jeho efektivitě a škálovatelnosti.

Otázka 6. Může být Big O Notation aplikován i na prostorovou složitost?

Odpovědět: Ano, Big O Notation lze také použít k analýze a popisu prostorové složitosti algoritmu s uvedením, kolik paměti vyžaduje vzhledem k velikosti vstupu.

Související článek:

• Příklady Big-O analýzy
• Návrh a analýza algoritmů
• Typy asymptotických zápisů v analýze složitosti algoritmů
• Analýza algoritmů | Velký – Ω (Big- Omega) zápis
• Analýza algoritmů | notace malé o a malé omega