Zápis Big O

Autor: Leandro Alegsa Dátum vytvorenia: 20. mája 2021

Zápis Big O je spôsob porovnávania algoritmov. Porovnáva ich tak, že vypočíta, koľko pamäte potrebujú a koľko času potrebujú na dokončenie.

Pri určovaní zložitosti problému sa často používa notácia Big O, ktorá je známa aj ako trieda zložitosti problému. Ako prvý použil tento zápis matematik Paul Bachmann (1837 - 1920) v druhom vydaní svojej knihy "Analytische Zahlentheorie" v roku 1896. Tento zápis spopularizoval Edmund Landau (1877 - 1938). Z tohto dôvodu, keď sa hovorí o Landauových symboloch, odkazuje sa na túto notáciu.

Notácia Big O je pomenovaná podľa termínu "poradie funkcie", ktorý sa vzťahuje na rast funkcií. Big O notácia sa používa na nájdenie hornej hranice (najvyššej možnej veľkosti) rýchlosti rastu funkcie, čo znamená, že sa v nej vypočíta najdlhší čas, ktorý bude potrebný na premenu vstupu na výstup. To znamená, že algoritmus možno zoskupiť podľa toho, ako dlho môže trvať v najhoršom prípade, keď sa zakaždým použije najdlhšia cesta.

Big O je výraz, ktorý zisťuje čas behu v najhoršom prípade a ukazuje, aký je algoritmus efektívny bez toho, aby bolo potrebné spustiť program na počítači. Je to užitočné aj preto, že rôzne počítače môžu mať rôzny hardvér, a preto potrebujú na jeho dokončenie rôzny čas. Keďže Big O vždy predpokladá najhorší prípad, môže ukázať konzistentné meranie rýchlosti: bez ohľadu na váš hardvér bude O ( 1 ) {\displaystyle O(1)} $O(1)$ vždy dokončený rýchlejšie ako O ( n ! ) {\displaystyle O(n!)} $O(n!)$ , pretože majú rôzne úrovne efektívnosti.

Príklady

Všetky nasledujúce príklady používajú kód napísaný v jazyku Python. Upozorňujeme, že toto nie je úplný zoznam typov Big O.

Neustále

O ( 1 ) {\displaystyle O(1)} $O(1)$ . Vždy trvá rovnako dlho bez ohľadu na vstup. Vezmime si napríklad funkciu, ktorá prijíma celé číslo (nazvané x) a vracia dvojnásobok jeho hodnoty:

def double(x): return x * 2 #Vráti hodnotu x krát 2

Po prijatí vstupu táto funkcia vždy urobí jeden krok, aby vrátila výstup. Je konštantný, pretože vždy zaberie rovnaký čas, takže je O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Lineárne

O ( n ) {\displaystyle O(n)} $O(n)$ . Zvyšuje sa podľa veľkosti vstupu reprezentovaného n {\displaystyle n} . Predpokladajme, že funkcia prijíma n a vracia každé číslo od 1 do n:

def count(n): i = 1 #Vytvorte počítadlo s názvom "i" s hodnotou 1 while i <= n: #Keď je i menšie alebo rovné n print(i) #Vytlačte hodnotu i i = i + 1 #Predefinujte i ako "hodnotu i + 1"

Ak by sme zadali hodnotu 5, potom by sa na výstupe zobrazilo 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,3,4,5} $1,2,3,4,5$ , čo si vyžaduje 5 cyklov na dokončenie. Podobne, ak by sme zadali hodnotu 100, vypisovalo by sa 1 , 2 , 3...98 , 99 , 100 {\displaystyle 1,2,3...98,99,100} $1,2,3...98,99,100$ , čo si vyžaduje dokončenie 100 cyklov. Ak je na vstupe n {\displaystyle n}, potom čas behu algoritmu je zakaždým presne n {\displaystyle n} cyklov, preto je O ( n ) {\displaystyle O(n)} $O(n)$ .

Faktoriálne

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ . Rastie vo faktorových množstvách, čo znamená, že potrebný čas sa masívne zvyšuje so vstupom. Napríklad povedzme, že chceme navštíviť päť miest na svete a chceme vidieť každé možné usporiadanie (permutáciu). Algoritmus, ktorý by sme mohli napísať pomocou knižnice itertools v jazyku Python, je nasledujúci:

import itertools #Import knižnice itertools cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Pole našich vybraných miest def permutations(cities): #Vzatie poľa miest ako vstupu: for i in itertools. permutations(cities): #pre každú permutáciu našich položiek (priradenú premennej "i") print(i) #Výstup i

Tento algoritmus vypočíta každú jedinečnú permutáciu našich miest a potom ju vypíše. Príklady výstupu budú zahŕňať:

("Londýn", "Paríž", "Berlín", "Amsterdam", "Rím") ("Londýn", "Paríž", "Berlín", "Rím", "Amsterdam") ("Londýn", "Paríž", "Amsterdam", "Berlín", "Rím") ... ("Rím", "Amsterdam", "Paríž", "Berlín", "Londýn") ("Rím", "Amsterdam", "Berlín", "Londýn", "Paríž") ("Rím", "Amsterdam", "Berlín", "Paríž", "Londýn")

Tu má náš vstupný zoznam 5 položiek a pri každom výbere sa naše zostávajúce možnosti zmenšia o 1. Inými slovami, našich 5 vstupov vyberá 5 × 4 × 3 × 2 × 1 {\displaystyle 5\times 4\times 3\times 2\times 1} $5\times 4\times 3\times 2\times 1$ položiek (alebo 5 ! {\displaystyle 5!} $5!$ ). Ak je náš vstup n {\displaystyle n} miest dlhý, potom počet výstupov je n ! {\displaystyle n! } $n!$ ; inými slovami, za predpokladu, že prejdeme každú permutáciu, budeme potrebovať O ( n ! ) {\displaystyle O(n!)} $O(n!)$ cyklov na jej dokončenie.

Zápis Little-o

Prísnejšia verzia Veľkého O je little-o. Rozdiel medzi veľkým O a little-o je v tom, že little-o je striktná horná hranica: zatiaľ čo O ( n ) {\displaystyle O(n)} $O(n)$ znamená, že čas dokončenia sa zvýši na toto maximum na základe veľkosti vstupu, o ( n ) {\displaystyle o(n)} $o(n)$ znamená, že čas dokončenia bude vo všeobecnosti nižší ako toto množstvo času. Inými slovami, Big O predpokladá, že každá slučka pôjde najdlhšou cestou a proces bude trvať čo najdlhšie, zatiaľ čo little-o je realistickejší, pokiaľ ide o skutočné časy behu; ak je počet slučiek založený na hode šesťstennou kockou, Big O bude vždy predpokladať hod 6, zatiaľ čo little-o zohľadní rovnakú pravdepodobnosť hodu iných čísel.

Otázky a odpovede

Otázka: Čo je to notácia Big O?

Odpoveď: Zápis Big O je spôsob porovnávania rýchlosti rastu rôznych funkcií, ktorý sa často používa na porovnávanie efektívnosti rôznych algoritmov výpočtom, koľko pamäte a času zaberie ich dokončenie. Môže sa použiť aj na určenie toho, aký zložitý je problém.

Otázka: Kto ako prvý použil tento zápis?

Odpoveď: Ako prvý použil tento zápis matematik Paul Bachmann (1837 - 1920) vo svojej knihe "Analytische Zahlentheorie" v roku 1896.

Otázka: Čo znamená veľké O?

Odpoveď: Big O znamená "rád funkcie", ktorý sa vzťahuje na rýchlosť rastu funkcií.

Otázka: Ako sa používa Big O?

Odpoveď: Zápis Big O sa používa na nájdenie hornej hranice (najvyššej možnej hodnoty) rýchlosti rastu funkcie, čo znamená, že určuje najdlhší čas, ktorý bude potrebný na premenu vstupu na výstup. To znamená, že algoritmy sa dajú zoskupiť podľa toho, ako dlho trvajú v najhoršom prípade, keď sa vždy zvolí najdlhšia cesta.

Otázka: Čo sú Landauove symboly?

Odpoveď: Landauove symboly sa vzťahujú na notáciu Big O, pomenovanú podľa Edmunda Landaua (1877 - 1938), ktorý túto notáciu spopularizoval.

Otázka: Prečo je užitočné Big O?

Odpoveď: Big O nám umožňuje merať rýchlosť bez toho, aby sme museli spúšťať programy na počítačoch, pretože vždy predpokladá najhorší možný scenár, vďaka čomu je konzistentný bez ohľadu na hardvérové rozdiely medzi počítačmi. Ukazuje tiež, aký je algoritmus efektívny bez toho, aby sme ho museli skutočne spustiť na počítači.