AlegsaOnline.com

Landauova notace

Autor: Leandro Alegsa

20-05-2021

Zápis Big O je způsob porovnávání algoritmů. Porovnává je tak, že vypočítá, kolik paměti je potřeba a kolik času trvá jejich dokončení.

Při určování složitosti problému se často používá notace Big O, známá také jako třída složitosti problému. Jako první tuto notaci použil matematik Paul Bachmann (1837-1920) ve druhém vydání své knihy "Analytische Zahlentheorie" v roce 1896. Notaci zpopularizoval Edmund Landau (1877-1938). Proto když se mluví o Landauových symbolech, odkazuje se na tuto notaci.

Notace Big O je pojmenována podle termínu "řád funkce", který se vztahuje k růstu funkcí. Notace Big O se používá k nalezení horní meze (nejvyšší možné velikosti) tempa růstu funkce, což znamená, že určuje nejdelší čas, který bude potřeba k přeměně vstupu na výstup. To znamená, že algoritmus lze seskupit podle toho, jak dlouho může trvat v nejhorším případě, kdy bude pokaždé zvolena nejdelší cesta.

Big O je výraz, který zjišťuje dobu běhu v nejhorším případě a ukazuje, jak efektivní je algoritmus, aniž by bylo nutné program spustit na počítači. To je užitečné i proto, že různé počítače mohou mít různý hardware, a proto potřebují k jeho dokončení různou dobu. Protože Big O vždy předpokládá nejhorší případ, může ukázat konzistentní měření rychlosti: bez ohledu na váš hardware bude O ( 1 ) {\displaystyle O(1)} $O(1)$ vždy dokončeno rychleji než O ( n ! ) {\displaystyle O(n!)} $O(n!)$ , protože mají různé úrovně efektivity.

Příklady

Všechny následující příklady používají kód napsaný v jazyce Python. Všimněte si, že toto není úplný seznam typů Big O.

Konstantní

O ( 1 ) {\displaystyle O(1)} $O(1)$ . Vždy trvá stejně dlouho bez ohledu na vstup. Vezměme například funkci, která přijímá celé číslo (nazvané x) a vrací dvojnásobek jeho hodnoty:

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

Po přijetí vstupu provede tato funkce vždy jeden krok a vrátí výstup. Je konstantní, protože bude vždy trvat stejně dlouho, takže je O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Lineární

O ( n ) {\displaystyle O(n)} $O(n)$ . Zvyšuje se podle velikosti vstupu, reprezentovaného n {\displaystyle n} . Předpokládejme, že funkce přijímá n a vrací každé číslo od 1 do n:

def count(n): i = 1 #Vytvoříme čítač "i" s hodnotou 1 while i <= n: #Když je i menší nebo rovno n print(i) #Vytiskněte hodnotu i i = i + 1 #Předefinujte i jako "hodnotu i + 1"

Pokud bychom zadali hodnotu 5, pak by se na výstupu objevily hodnoty 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,3,4,5}. $1,2,3,4,5$ , což vyžaduje dokončení 5 cyklů. Podobně pokud bychom zadali hodnotu 100, vypsalo by to 1 , 2 , 3...98 , 99 , 100 {\displaystyle 1,2,3...98,99,100} $1,2,3...98,99,100$ , což vyžaduje dokončení 100 smyček. Pokud je na vstupu n {\displaystyle n}, pak je doba běhu algoritmu pokaždé přesně n {\displaystyle n} cyklů, tedy je O ( n ) {\displaystyle O(n)} $O(n)$ .

Faktoriální

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ . Zvyšuje se ve faktorových hodnotách, což znamená, že čas potřebný k výpočtu se masivně zvyšuje se vstupem. Řekněme například, že chceme navštívit pět měst na světě a chceme vidět všechna možná pořadí (permutace). Algoritmus, který bychom mohli napsat pomocí knihovny itertools v jazyce Python, je následující:

import itertools #Import knihovny itertools cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Pole našich vybraných měst def permutations(cities): #Přijmeme pole měst jako vstup: for i in itertools. permutations(cities): #Pro každou permutaci našich položek (přiřazenou proměnné "i") print(i) #Výstup i

Tento algoritmus vypočítá každou jedinečnou permutaci našich měst a poté ji vypíše. Příklady výstupů budou zahrnovat:

("Londýn", "Paříž", "Berlín", "Amsterdam", "Řím") ("Londýn", "Paříž", "Berlín", "Řím", "Amsterdam") ("Londýn", "Paříž", "Amsterdam", "Berlín", "Řím") ... ("Řím", "Amsterdam", "Paříž", "Berlín", "Londýn") ("Řím", "Amsterdam", "Berlín", "Londýn", "Paříž") ("Řím", "Amsterdam", "Berlín", "Paříž", "Londýn")

Zde je náš vstupní seznam dlouhý 5 položek a pro každý výběr se naše zbývající možnosti zmenší o 1. Jinými slovy, našich 5 vstupů vybírá 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žek (nebo 5 ! {\displaystyle 5!} $5!$ ). Pokud je náš vstup dlouhý n {\displaystyle n} měst, pak počet výstupů je n ! {\displaystyle n! } $n!$ ; jinými slovy, za předpokladu, že projdeme každou permutaci, budeme k jejímu dokončení potřebovat O ( n ! ) {\displaystyle O(n!)} $O(n!)$ cyklů.

Zápis Little-o

Přísnější verze Velkého O je little-o. Rozdíl mezi velkým O a little-o spočívá v tom, že little-o je striktní horní hranice: zatímco O ( n ) {\displaystyle O(n)} $O(n)$ znamená, že čas dokončení se zvýší na toto maximum v závislosti na velikosti vstupu, o ( n ) {\displaystyle o(n)} $o(n)$ znamená, že čas dokončení bude obecně pod touto hodnotou. Jinými slovy, Big O předpokládá, že každá smyčka půjde nejdelší cestou a proces bude trvat co nejdéle, zatímco little-o je realističtější, pokud jde o skutečné časy běhu; pokud je počet smyček založen na hodu šestistěnnou kostkou, Big O bude vždy předpokládat, že padne 6, zatímco little-o zohlední stejnou pravděpodobnost, že padnou i jiná čísla.

Otázky a odpovědi

Otázka: Co je to notace Big O?

Odpověď: Notace Big O je způsob porovnávání rychlosti růstu různých funkcí, který se často používá k porovnávání efektivity různých algoritmů tím, že se vypočítá, kolik paměti a času zabere jejich dokončení. Lze ji také použít k určení, jak složitý je problém.

Otázka: Kdo jako první použil tento zápis?

Odpověď: Jako první použil tento zápis matematik Paul Bachmann (1837-1920) ve své knize "Analytische Zahlentheorie" v roce 1896.

Otázka: Co znamená Big O?

A: Big O znamená "řád funkce", který se vztahuje k rychlosti růstu funkcí.

Otázka: Jak se používá Big O?

Odpověď: Zápis Big O se používá k nalezení horní meze (nejvyšší možné hodnoty) rychlosti růstu funkce, což znamená, že se zjistí nejdelší doba, za kterou se vstup promění ve výstup. To znamená, že algoritmy lze rozdělit do skupin podle toho, jak dlouho jim to trvá v nejhorším případě, kdy se pokaždé zvolí nejdelší cesta.

Otázka: Co jsou Landauovy symboly?

Odpověď: Landauovy symboly odkazují na notaci Big O, pojmenovanou po Edmundu Landauovi (1877-1938), který tuto notaci zpopularizoval.

Otázka: Proč je Big O užitečný?

Odpověď: Big O nám umožňuje měřit rychlost bez nutnosti spouštět programy na počítačích, protože vždy předpokládá nejhorší možný scénář, takže je konzistentní bez ohledu na hardwarové rozdíly mezi počítači. Ukazuje také, jak je algoritmus efektivní, aniž bychom ho museli skutečně spustit na počítači.