"O" velké a "o" malé
"O" velké a "o" malé ( a ) jsou matematické zápisy pro porovnávání asymptotického chování (asymptotiky) funkcí . Používají se v různých odvětvích matematiky, ale nejaktivněji - v matematické analýze , teorii čísel a kombinatorice , stejně jako v informatice a teorii algoritmů . Asymptotika je chápána jako povaha změny funkce, protože její argument směřuje k určitému bodu.
![Ó](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d70e1d0d87e2ef1092ea1ffe2923d9933ff18fc)
![Ó](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c1031f61947aa3d1cf3a70ec3e4904df2c3675d)
, " o malé z " znamená "nekonečně malé vzhledem k " [1] , zanedbatelné při zvažování . Význam termínu "Big O" závisí na oblasti jeho použití, ale vždy neroste rychleji než (přesné definice jsou uvedeny níže).
![F](https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61)
![F](https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61)
![F](https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61)
![Z)](https://wikimedia.org/api/rest_v1/media/math/render/svg/152bb1f6a17b0186d40c911c4848704fdc840133)
![F](https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61)
Zejména:
- fráze " složitost algoritmu je " znamená, že se zvýšením parametru charakterizujícího množství vstupních informací algoritmu se doba běhu algoritmu nezvýší rychleji, než se vynásobí nějakou konstantou;
![O(f(n))](https://wikimedia.org/api/rest_v1/media/math/render/svg/756b4d8648334719f65bf5e6269c7a2b3a502f13)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![f(n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/c1c49fad1eccc4e9af1e4f23f32efdc3ac4da973)
- fráze "funkce je" o "malá funkce v blízkosti bodu " znamená, že jak se přibližuje k , klesá rychleji než (poměr směřuje k nule).
![f(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074)
![g(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59)
![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
![X](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
![f(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074)
![g(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59)
![\left |f(x)\vpravo |/\left |g(x)\vpravo |](https://wikimedia.org/api/rest_v1/media/math/render/svg/36ec51fb87c55976ca154b2826df2020a1cff601)
Definice
Dovolit a být dvě funkce definované v některých proražených okolí bodu , a v tomto okolí nezmizí. Říká se, že:
![f(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074)
![g(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59)
![x_{0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86f21d0e31751534cd6584264ecf864a6aa792cf)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3556280e66fe2c0d0140df20935a6f057381d77)
je "O" větší než when , pokud existuje taková konstanta , že pro všechny z nějakého okolí bodu platí nerovnost
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3556280e66fe2c0d0140df20935a6f057381d77)
![x\do x_0](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ffbf95eb25f9fae501b6beaf31d0728fba4c451)
![C>0](https://wikimedia.org/api/rest_v1/media/math/render/svg/c84d4126c6df243734f9355927c026df6b0d3859)
![X](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
![x_{0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86f21d0e31751534cd6584264ecf864a6aa792cf)
;
je "o" malé z na , pokud pro nějaký existuje tak proražené okolí bodu , že nerovnost platí
pro všechny![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3556280e66fe2c0d0140df20935a6f057381d77)
![x\do x_0](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ffbf95eb25f9fae501b6beaf31d0728fba4c451)
![\varepsilon >0](https://wikimedia.org/api/rest_v1/media/math/render/svg/e04ec3670b50384a3ce48aca42e7cc5131a06b12)
![U_{x_0}'](https://wikimedia.org/api/rest_v1/media/math/render/svg/2965d6ac3466de0da720888cbab7c6dda5abc2d0)
![x_{0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86f21d0e31751534cd6584264ecf864a6aa792cf)
![x\in U_{x_0}'](https://wikimedia.org/api/rest_v1/media/math/render/svg/af1c502ee813b3213e27b71cb37b3bbd743e0f5e)
![|f(x)| < \varepsilon |g(x)|.](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c3134a4975113825f3d17f7e77821db2924543c)
Jinými slovy, v prvním případě je poměr v blízkosti bodu (to znamená, že je ohraničen shora) a ve druhém případě má tendenci k nule v .
![{\displaystyle {\frac {|f|}{|g|}}\leqslant C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c8399c3df2aee8ee5b35293ed6ce97eaea4344f)
![x_{0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86f21d0e31751534cd6584264ecf864a6aa792cf)
![x\do x_0](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ffbf95eb25f9fae501b6beaf31d0728fba4c451)
Označení
Obvykle se výraz " je velký ( malý) z " zapisuje pomocí rovnosti (respektive ).
![F](https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61)
![Ó](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d70e1d0d87e2ef1092ea1ffe2923d9933ff18fc)
![Ó](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c1031f61947aa3d1cf3a70ec3e4904df2c3675d)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3556280e66fe2c0d0140df20935a6f057381d77)
![f(x) = O(g(x))](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e69c69cb5dc8e33a50a094deff53ec988fa6aeb)
![f(x) = o(g(x))](https://wikimedia.org/api/rest_v1/media/math/render/svg/66122afa55c2aa7af3f23d3caa66a5a6ca4a494c)
Tento zápis je velmi pohodlný, ale vyžaduje určitou opatrnost při jeho používání (a proto se mu lze v nejzákladnějších učebnicích vyhnout). Faktem je, že se nejedná o rovnost v obvyklém smyslu, ale o asymetrický vztah .
Zejména lze psát
![f(x) = O(g(x))](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e69c69cb5dc8e33a50a094deff53ec988fa6aeb)
(nebo ),
ale výrazy
![O(g(x)) = f(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/92367a19ef0df3bb11bb76bb211e548608b43a05)
(nebo )
bezvýznamný.
Další příklad: pokud je to pravda
![x\rightarrow 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7e11497fe1908e690aef1eee0f4200e71e0eb9d)
ale
![{\displaystyle o(x)\neq O(x^{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4240b190bc1ec6595af619f53661e9d64080d1bb)
.
Neboť jakékoli x je pravdivé
![o(x) = O(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/97fac554ae0318ebd1e8b107c37c670b1bd65863)
,
to znamená, že nekonečně malé množství je ohraničené, ale
Místo rovnítka by bylo metodologicky správnější používat znaky příslušnosti a inkluze, chápání a jako označení pro množiny funkcí, tedy používat zápis ve tvaru
![Ó({\,})](https://wikimedia.org/api/rest_v1/media/math/render/svg/4bc9c8c16db333493ef9376f5d494cec9775e58a)
![Ó({\,})](https://wikimedia.org/api/rest_v1/media/math/render/svg/927ddfe1977269f138ed01cd1835433ab1e3eef3)
nebo
místo, resp.
a
V praxi je však takový záznam extrémně vzácný, hlavně v těch nejjednodušších případech.
Při použití těchto zápisů musí být výslovně uvedeno (nebo z kontextu zřejmé), o která okolí (jednostranná nebo oboustranná; obsahující celá, reálná, komplexní nebo jiná čísla) a o jaké přípustné množiny funkcí se jedná (protože stejné zápis se používá ve vztahu k funkcím více proměnných, k funkcím komplexní proměnné, k maticím atd.).
Další podobná označení
Následující zápis se používá
pro funkce a pro :![f(n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/c1c49fad1eccc4e9af1e4f23f32efdc3ac4da973)
![g(n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4ad18070e494503403daf39398e711c1378348e)
![n \ až n_0](https://wikimedia.org/api/rest_v1/media/math/render/svg/8eaa6f6d6d5be9107ff4ac3268ea96561c926e90)
Označení
|
Intuitivní vysvětlení
|
Definice
|
|
je shora omezena funkcí (až do konstantního činitele) asymptoticky
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3556280e66fe2c0d0140df20935a6f057381d77) |
|
|
je zdola omezena funkcí (až do konstantního faktoru) asymptoticky
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3556280e66fe2c0d0140df20935a6f057381d77) |
|
|
ohraničený zdola i shora funkcí asymptoticky
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3556280e66fe2c0d0140df20935a6f057381d77) |
|
|
dominuje asymptoticky
![F](https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61) |
|
|
dominuje asymptoticky
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3556280e66fe2c0d0140df20935a6f057381d77) |
|
|
je ekvivalentní asymptoticky
|
|
kde je proražené okolí bodu .
![U](https://wikimedia.org/api/rest_v1/media/math/render/svg/458a728f53b9a0274f059cd695e067c430956025)
![n_{0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63584d203ecb012a7bcb90f422408bbfe4018956)
Základní vlastnosti
Tranzitivita
Reflexivita
;
;
![f(n)=O(f(n))](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a78c49d28d64f20516dda0ecc9cf81fb89cec59)
Symetrie
Permutační symetrie
Ostatní
![O(C \cdot f) = O(f)](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9428614b18641e2db457f6868f2f8cf1e9ac55b)
a v důsledku toho
Asymptotický zápis v rovnicích
- Pokud pravá strana rovnice obsahuje pouze asymptotický zápis (například ), pak rovnítko označuje příslušnost k množině ( ).
![n=O(n^{2})](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8871bef11a3b7e1f525d3f71763ffbe24116158)
![n\in O(n^{2})](https://wikimedia.org/api/rest_v1/media/math/render/svg/136df0ae2f59aa511638b245c14dfc3214783411)
- Pokud se asymptotický zápis vyskytuje v rovnici v jiné situaci, považuje se za substituční některé funkce. Například jako x → 0 vzorec znamená, že , kde je funkce, o které je známo pouze to, že patří do množiny . Předpokládá se, že takových funkcí je ve výrazu tolik, kolik je v něm asymptotických zápisů. Například - obsahuje pouze jednu funkci z .
![e^x-1 = x + o(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/36c917974e69e5e3c111f689e0b823d6aa9139ba)
![e^x-1 = x + f(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/254bb0db2c179f3d0912ce0d77f4b8e6ad655cdf)
![f(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074)
![vůl)](https://wikimedia.org/api/rest_v1/media/math/render/svg/893488c26042998c6368d70fd28334ba7ccfc7f0)
![\sum_{i=0}^nO(n_i^2)](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4ea2a29c6bce038a46b53e5e40fa4e0732d6447)
![O(n^{2})](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd9594a16cb898b8f2a2dff9227a385ec183392)
- Pokud se asymptotický zápis vyskytuje na levé straně rovnice, použije se následující pravidlo:
jakoukoli funkci zvolíme (podle předchozího pravidla) místo asymptotického zápisu na levé straně rovnice, můžeme zvolit funkce místo asymptotický zápis (podle předchozího pravidla) na pravé straně tak, aby rovnice byla správná .
Záznam například znamená, že pro jakoukoli funkci existuje nějaká funkce , takže výraz je pravdivý pro všechny .![x+o(x)=O(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/b1d7d4cd329f8759ed1de1fd78e89d73794089e4)
![f(x)\in o(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5dad5021e409aec5ecfa5d607795843ef308100)
![g(x)\in O(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/521d2674e22a4a01b9bc4b66ec6ee1a56c7b441c)
![x+f(x)=g(x)](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d11861a72f85eb85ac09f01ea91e0462826d2c6)
![X](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
- Některé z těchto rovnic lze spojit do řetězců. Každá z rovnic by v tomto případě měla být interpretována v souladu s předchozím pravidlem.
Například: . Všimněte si, že takový výklad implikuje naplnění vztahu .![4n^4+4n^2+1=4n^4+\Theta(n^2)=\Theta(n^4)](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9b1f6608c786ab7e55bf1ccc6c4dd3bb59034fb)
![4n^4+4n^2+1=\Theta(n^4)](https://wikimedia.org/api/rest_v1/media/math/render/svg/092c67744e42ae6490ee4294464e846c98f1621d)
Výše uvedený výklad implikuje naplnění vztahu:
![\vlevo, odjet. \begin{matice}A = B \\ B = C \end{matrix} \right\} \Šipka doprava A = C](https://wikimedia.org/api/rest_v1/media/math/render/svg/340b480042332913368ec0a8fa2467c76ca06c45)
, kde A , B , C jsou výrazy, které mohou obsahovat asymptotický zápis.
Příklady použití
v .![x\rightarrow 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7e11497fe1908e690aef1eee0f4200e71e0eb9d)
v .![n \rightarrow \infty](https://wikimedia.org/api/rest_v1/media/math/render/svg/9702f04f2d0e5b887b99faeeffb0c4cfd8263eee)
Když je nerovnost splněna . Takže dáme .
![n>1](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee74e1cc07e7041edf0fcbd4481f5cd32ad17b64)
![(n+1)^2<4n^2](https://wikimedia.org/api/rest_v1/media/math/render/svg/525b78cd32ce5bd4fac25a281f9c7d077abed21d)
![n_0=1, c=4](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff12a60bd4c3aafefc92b22653ad87d80d88574c)
Všimněte si, že nemůžeme dát , protože , a proto je tato hodnota větší než , pro jakoukoli konstantu .
![n_{0}=0](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac9889aa38e1fa54d522137594d424a2cd95fb1b)
![T(0)=1](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0db9b6b2df11163261cc2359eaedb7f6c1b4ab3)
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/86a67b81c2de995bd608d5b2df50cd8cd7d92455)
- Funkce pro má určitý stupeň růstu .
![T(n)=3n^3+2n^2](https://wikimedia.org/api/rest_v1/media/math/render/svg/159522b3898d7c30b317c86a7916e93b3b4399c3)
![n \rightarrow \infty](https://wikimedia.org/api/rest_v1/media/math/render/svg/9702f04f2d0e5b887b99faeeffb0c4cfd8263eee)
![O(n^{3})](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b04f5c5cfea38f43406d9442387ad28555e2609)
Abychom to ukázali, musíme vložit a . Dá se samozřejmě říci, že to má řád , ale toto je slabší tvrzení než toto .
![n_{0}=0](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac9889aa38e1fa54d522137594d424a2cd95fb1b)
![c=5](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ce4e75712503e12852c7b4b9cafd1b048744955)
![T(n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/0be5a46684e1279c27414b285fa995f30407d002)
![O(n^{4})](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae98b94e039c8eafabf6fe6a0128d232ed7d21f6)
- Dokažme, že funkce for nemůže mít pořadí .
![3^n](https://wikimedia.org/api/rest_v1/media/math/render/svg/193abd21d79ceb2992929ab3b3a1ee97d2afb6a0)
![n \rightarrow \infty](https://wikimedia.org/api/rest_v1/media/math/render/svg/9702f04f2d0e5b887b99faeeffb0c4cfd8263eee)
![O(2^n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4b1a4ff0bc4f81ebf79f28260c6fb54ee08ff8d)
Předpokládejme, že existují konstanty a takové, že nerovnost platí pro všechny .
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/86a67b81c2de995bd608d5b2df50cd8cd7d92455)
![n_{0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63584d203ecb012a7bcb90f422408bbfe4018956)
![n \geq n_0](https://wikimedia.org/api/rest_v1/media/math/render/svg/fff23d9c13da1b2a7ec6f7fab8fa413b129c6b6c)
![3^n \leq c \cdot 2^n](https://wikimedia.org/api/rest_v1/media/math/render/svg/2feef6bfb394fa87812d766ab9a559a29bab585a)
Pak pro všechny . Ale nabývá jakékoli hodnoty, libovolně velké, pro dostatečně velké , takže neexistuje žádná taková konstanta , která by mohla být větší pro všechny velké z některých .
![c \geq \left( \frac{3}{2} \right)^n](https://wikimedia.org/api/rest_v1/media/math/render/svg/37ba08eb19cb7894c2c16b5dafbe668f51997df8)
![n \geq n_0](https://wikimedia.org/api/rest_v1/media/math/render/svg/fff23d9c13da1b2a7ec6f7fab8fa413b129c6b6c)
![\left( \frac{3}{2} \right)^n](https://wikimedia.org/api/rest_v1/media/math/render/svg/4289f62b3563f13d1357d9fee9b7544afda50a23)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/86a67b81c2de995bd608d5b2df50cd8cd7d92455)
![\left( \frac{3}{2} \right)^n](https://wikimedia.org/api/rest_v1/media/math/render/svg/4289f62b3563f13d1357d9fee9b7544afda50a23)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
.
Pro kontrolu stačí dát . Pak pro .
![c=1](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e3467f9e219a5ea38a30da5c3a02c2c23f61a79)
![T(n) \geq cn^3](https://wikimedia.org/api/rest_v1/media/math/render/svg/4696111068f642456e751509c893295c0e67b387)
Historie
Zápis „O“ je velký, zavedl jej německý matematik Paul Bachmann ve druhém díle své knihy „Analytische Zahlentheorie“ (Analytická teorie čísel), vydané v roce 1894 . Zápis "o malý" byl poprvé použit dalším německým matematikem Edmundem Landauem v roce 1909 ; popularizace obou označení souvisí i s pracemi posledně jmenovaných, v souvislosti s nimiž se jim také říká Landauovy symboly . Označení pochází z německého slova „Ordnung“ (řád) [2] .
Viz také
Poznámky
- ↑ Shvedov I. A. Kompaktní kurz matematické analýzy. Část 1. Funkce jedné proměnné. - Novosibirsk, 2003. - S. 43.
- ↑ D.E. Knuth. Velký Omicron a velká Omega a velká Theta : Článek . - ACM Sigact News, 1976. - V. 8 , č. 2 . - S. 18-24 . Archivováno z originálu 15. srpna 2016.
Literatura
- D. Green, D. Knuth. Matematické metody pro analýzu algoritmů. — Per. z angličtiny. — M .: Mir, 1987. — 120 s.
- J. McConnell. Základy moderních algoritmů. - Ed. 2 další - M .: Technosfera, 2004. - 368 s. — ISBN 5-94836-005-9 .
- John E. Savage. Složitost výpočtů. - M. : Factorial, 1998. - 368 s. — ISBN 5-88688-039-9 .
- V. N. Krupský. Úvod do výpočetní složitosti. - M. : Factorial Press, 2006. - 128 s. — ISBN 5-88688-083-6 .
- Herbert S. Wilf. Algoritmy a složitosti .
- Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitola 3. Růst funkcí // Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M .: Williams, 2005. - S. 87-108. — ISBN 5-8459-0857-4 .
- Bugrov, Nikolský. Vyšší matematika, svazek 2.
- Dionysis Zindros. Úvod do analýzy složitosti algoritmů (2012). Získáno 11. října 2013. Archivováno z originálu 10. října 2013. (Ruština)