Téma t4: Algoritmy od nuly (do $n$)

Zadáno v čísle 25.1.

Zadání

Stavíme počítač

Slovo úvodem

Jak je již z názvu patrné, v našem témátku se budeme zabývat algoritmy. Co je to takový algoritmus? Žádná oficiální definice neexistuje. Dá se třeba říct, že je to přesný popis postupu, jak něco udělat. V tomto pojetí by algoritmem mohl být třeba dobře popsaný recept na smažení palačinek nebo návod na složení židle z IKEA. My se ale omezíme pouze na algoritmy, které jsou ve výsledku určeny pro zpracování počítačem. Po počítači nemůžeme chtít, aby nám usmažil palačinky (tedy, chtít to samozřejmě můžeme). Co po něm naopak chtít budeme, je například sečíst dvě čísla nebo určit, jestli se v posloupnosti čísel vyskytuje dané číslo. Náš algoritmus bude mít vždy vstup (data, se kterými má počítat) a výstup (výsledek). V případě prvního algoritmu by tedy vstupem byla dvě čísla a výstupem jejich součet, vstupem pro druhý algoritmus by byla posloupnost $n$ čísel a hledané číslo $k$ a výstupem informace, zda se číslo $k$ v posloupnosti vyskytuje, případně na které pozici.

Během řešení témátka se budeme snažit pro různé problémy vymyslet algoritmy, které vždy nejen vypíší správný výsledek, ale udělají to v co nejkratším čase. Algoritmus, který odpovídá vždy správně, ale výpočet by mu na dnešních počítačích již pro krátké vstupy trval několik miliard let, pro nás, jak jistě uznáte, není příliš užitečný (a brzy uvidíte, že omylem vymyslet takový algoritmus není vůbec složité).

Při vymýšlení algoritmů budeme, jak název napovídá, začínat úplně od nuly. Body tedy dáváme za to, že jste vymysleli řešení, a ne za sepsání algoritmu, který jste již dobře znali. Také věříme, že M&Mko řešíte hlavně proto, abyste se něco nového naučili (a ne jen kvůli bodům). Pokud tedy řešení některých zde zmíněných problémů znáte, pusťte se raději do jiného témátka nebo jiné úložky tohoto témátka, které pro vás budou větší výzvou, nebo si vhodnou úložku k řešení sami vymyslete.

Počítač

Algoritmy nebudeme spouštět na skutečném počítači – museli bychom brát ohled na spoustu technických detailů, které by nám zabraňovaly soustředit se na samotný algoritmus. Místo toho si tedy vymyslíme vlastní teoretický model počítače. Budeme od něj chtít, aby byl co nejjednodušší a aby zároveň jeho fungování co nejlépe odpovídalo skutečnému počítači (tedy aby algoritmy, které jsou na něm rychlé, byly rychlé i na skutečném počítači a naopak).

Protože zavést takový model od nuly dá trochu práci, ukážeme vám nejdříve jeho verzi, která bude obsahovat o trochu pokročilejší konstrukce, zato bude jednodušší na pochopení a používání. Nemusíte se ale bát, že bychom vás o skutečně minimalistický model ochudili – naleznete ho na konci tohoto textu.

Náš počítač má paměť, do které si můžeme ukládat proměnné. Proměnná má vždy nějaké jméno a je v ní uloženo jedno celé číslo. Počítač umí počítat (tedy provádět operace $+$, $-$, $\cdot $, $/$) s čísly uloženými v proměnných a přiřazovat je do jiných proměnných. Protože umíme do proměnných ukládat jen celá čísla, funguje dělení jako dělení se zbytkem, ale zbytek se nikam neukládá (tedy $8/3 = 2$). Na první pohled by se mohlo zdát, že je velmi omezující, že umíme pracovat pouze s celými čísly. Můžete si ale zkusit rozmyslet, že třeba text nebo racionální čísla se dají jednoduše zakódovat pomocí celých čísel.

Když chceme na našem modelu něco spočítat, rozepíšeme náš algoritmus jako jednotlivé instrukce, které má počítač provést, dáme mu je a on je postupně jednu po druhé provádí. Takovému seznamu instrukcí říkáme kód nebo program. Může vypadat například takto:

  1.     a $\gets $ 4 (do proměnné a přiřaď číslo 4)
  2.     b $\gets $ 5 (do proměnné b přiřaď 5)
  3.     soucet $\gets $ a $+$ b (do proměnné soucet přiřaď součet a $+$ b, tedy číslo 9)

Náš program sčítá čísla. Sčítá ale vždy jen čísla 4 a 5, což není moc užitečné. Potřebovali bychom, aby náš algoritmus (sečtení dvou čísel) šlo spustit pro libovolný vstup (tedy pro libovolná 2 čísla) a nemuseli jsme kvůli tomu psát pokaždé nový program. V praxi bychom museli vstup nějak načíst (třeba z klávesnice či souboru). My budeme předpokládat, že máme instrukci na načtení čísla ze vstupu a vypsání čísla nebo textu na výstup. Program tedy bude vypadat následovně:

  1.     a $\gets $ přečti číslo
  2.     b $\gets $ přečti číslo
  3.     soucet $\gets $ a $+$ b
  4.     Vypiš soucet

Vezměme si nyní další problém z úvodu tohoto textu. Chceme najít určené číslo v posloupnosti délky $n$. Abychom mohli problém vyřešit, museli bychom jako vstup dostat kromě čísla $n$ a čísla, které hledáme, ještě dalších $n$ proměnných – prvky posloupnosti. Stejně tak na výstup bychom někdy mohli potřebovat vypsat třeba $n$ proměnných. Pojmenovávání $n$ proměnných by bylo poněkud nepraktické, proto si zavedeme konstrukt, kterému budeme říkat pole. Pole je prostě pojmenovaná posloupnost celých čísel, která má předem určenou délku. V informatice je zvykem číslovat prvky pole od nuly a my budeme tento zvyk dodržovat. K prvkům pole budeme přistupovat tak, že za název pole napíšeme pozici příslušného prvku, tedy např. seznam[8] je devátý prvek v poli seznam (protože číslujeme od nuly). Jednotlivé prvky pole se pak chovají jako proměnné, a můžeme s nimi tedy dělat to, co s proměnnými – sčítat, odčítat, násobit, dělit (celočíselně), přiřazovat do nich, ale nejde třeba naráz přičíst jedničku ke všem číslům v poli. Pole navíc umí oproti proměnným to, že ho můžeme indexovat proměnnou. Tedy pokud je třeba v proměnné a hodnota 8, pak seznam[a] je to samé, co seznam[8]. Také nesmíme zapomenout, že u pole musí být určena maximální délka, nemůžeme tedy pole rovnou používat (jak to děláme u proměnných), ale musíme počítači napřed říct, aby vyrobil pole dané délky, tedy např. „vyrob pole seznam délky $n$“ a až poté „seznam[i] $\gets $ 13“.

Chybí nám ještě poslední dvě instrukce – podmínka a cyklus.

Podmínka obsahuje nějaký výraz, u kterého lze určit, zda je, či není pravdivý. Výraz má tvar „proměnná nebo číslo $<$, $>$, $\ge $, $\le $, $=$ jiná proměnná nebo číslo“ (např. a $>$ 0). Můžeme také použít negaci a spojit více výrazů pomocí OR, nebo AND1. Pod podmínku pak napíšeme část kódu, která se má provést, pokud podmínka platí, a volitelně i část kódu, která se má provést, pokud podmínka neplatí. Můžeme tedy napsat:

  1.     a $\gets $ vstup
  2.     Pokud (a$/$2)$\cdot $2 $=$ a:
  3.         Vypiš „Vstup je sudý“
  4.     Jinak:
  5.         Vypiš „Vstup je lichý“

Všimněme si, že u lichých čísel se podíl při dělení dvojkou zaokrouhlí dolů, a tedy opravdu nenastane v podmínce rovnost.

Nyní si zavedeme další konstrukt. Budeme mu říkat cyklus a vypadá následovně: Dokud platí „podmínka“, tak dělej „část kódu, která se má provádět“. Cyklus můžeme použít například k napsání programu, který násobí dvě přirozená čísla, aniž by použil operaci násobení.

  1.     a $\gets $ vstup
  2.     b $\gets $ vstup
  3.     pocetScitani $\gets $ 0
  4.     soucin $\gets $ 0
  5.     Dokud (pocetScitani $<$ b) tak:
  6.         soucin $\gets $ soucin $+$ a
  7.         pocetScitani $\gets $ pocetScitani $+$ 1
  8.     Vypiš soucin

To je zatím k našemu modelu vše. Pojďme si teď zkusit nějaký užitečný algoritmus napsat.

Algoritmus – hledání čísla v poli

Nyní si ukážeme jednoduchý algoritmus, který zjistí, zda se v posloupnosti čísel nachází číslo 42. (Zatím nás nebude zajímat, na které pozici je. Můžete si rozmyslet, jak algoritmus upravit, abychom pozici zjistili.) Budeme předpokládat, že víme, kolik čísel dostaneme. Pomocí cyklu si pak ze vstupu uložíme čísla do pole. (Tento technický detail nebudeme pokaždé zmiňovat – dále už budeme vždy předpokládat, že vstup máme na začátku uložen v paměti.)

Pomocí cyklu budeme postupně procházet celé pole. Vytvoříme si proměnné pozice a nalezeno. V proměnné pozice si budeme pamatovat pozici v poli, na které zrovna hledáme číslo 42 a kterou po každém průchodu cyklem zvýšíme o jedna. Takovou proměnnou potřebujeme, abychom věděli, jak v podmínce cyklu otestovat, zda máme pokračovat. V proměnné nalezeno bude na začátku 0 symbolizující, že jsme 42 ještě nenalezli, a když ji najdeme, nastavíme tuto proměnnou na hodnotu 1. V každém průchodu cyklem pak podmínkou zkontrolujeme, zda na pozici dané proměnnou pozice není číslo 42. Pokud je, tak proměnnou nalezeno nastavíme na 1, jinak jí necháme původní hodnotu. Po doběhnutí programu tedy můžeme díky proměnné nalezeno zjistit, zda jsme číslo 42 našli, nebo nenašli.

Celý algoritmus by tedy vypadal asi následovně:

     Vstup: posloupnost čísel v poli posloupnost a jejich počet v proměnné n

  1.     pozice $\gets $ 0
  2.     nalezeno $\gets $ 0
  3.     Dokud pozice $<$ n:
  4.         Pokud posloupnost[pozice] $=$ 42:
  5.             nalezeno $\gets $ 1
  6.     pozice $\gets $ pozice $+$ 1

     Výstup: Proměnná nalezeno, ve které je uložena 1, právě pokud je číslo 42
v posloupnosti obsaženo

Můžeme si navíc všimnout, že jsme k ničemu nepoužili to, že jsme hledané číslo znali předem, a že jsme na řádce 4 mohli kontrolovat rovnost s proměnnou, ve které by bylo uložené hledané číslo. Umíme takto tedy zjistit, zda je v poli libovolné číslo uložené v proměnné.

Časová složitost

V úvodu jsme tvrdili, že se budeme snažit vymýšlet algoritmy, které spočtou výsledek v co nejkratším čase. Co to ale na našem novém počítači vlastně znamená? Protože na teoretickém modelu jen těžko můžeme měřit čas běhu programu, budeme místo toho počítat provedené instrukce. Vztah ke skutečným počítačům je zde zřejmý – skutečné procesory opravdu mají sadu instrukcí (do kterých je každý program přeložen) a vykonat jednu instrukci trvá nějakou krátkou dobu. Počet vykonaných instrukcí tedy nějakým způsobem odpovídá době běhu programu.

Za instrukci považujeme některou z operací $\gets $ (přiřazení), $+$, $-$, $\cdot $, $/$ nebo určení pravdivostní hodnoty jednoduchého výrazu.

Můžete se pokusit spočítat, kolik instrukcí provede výše popsaný algoritmus (nezapomeňte, že některé instrukce uvnitř cyklu bude počítač provádět $n$-krát). Už jen to, že se autoři tohoto textu nejsou schopni shodnout, zda to vyjde $4n+4$, nebo $6n+3$, napovídá, že spočítat přesný počet instrukcí není vůbec jednoduché a u složitějších algoritmů téměř nemožné. Navíc když spustíme program na skutečném počítači, závisí počet instrukcí na tom, jak přesně funguje procesor daného stroje. Počítače jsou také ve skutečnosti různě rychlé, takže stejná instrukce bude trvat na různých počítačích různě dlouho. Co s tím? Místo toho, abychom počítali přesný počet instrukcí, budeme ho počítat jen zhruba. Konkrétně nebudeme řešit konstanty, kterými $n$ násobíme a které k němu přičítáme. Důvodem, proč to není zas tak špatné řešení, je, že když bude vstup dostatečně dlouhý (a tedy $n$ dostatečně velké), budou konstanty zanedbatelně velké vůči něčemu, co závisí na $n$. Například pokud porovnáme časové složitosti $20n$ a $3n^2$, tak vidíme, že již pro poměrně malá $n$ budou konstanty zanedbatelné vzhledem k rozdílu způsobenému kvadratickou funkcí.

V našem algoritmu závisí počet instrukcí na $n$ lineárně – počet provedených instrukcí je nejvýše přímo úměrný počtu čísel na vstupu. Není těžké si uvědomit, že rychlejší algoritmus nemůže existovat – na každé z $n$ zadaných čísel se totiž musíme alespoň jednou podívat a jen na to potřebujeme alespoň $n$ instrukcí.

Abychom si tedy ulehčili práci a nemuseli jsme počet instrukcí počítat přesně, zavádíme takzvanou „óčkovou notaci“2. Óčková notace je horní odhad na počet instrukcí, které algoritmus provede, pokud zanedbáme multiplikativní konstanty a spustíme ho pro dostatečně velký vstup. 3 Pokud má tedy algoritmus časovou složitost $\mathcal{O}(n^2)$, znamená to, že pro dostatečně velká $n$ existuje konstanta $k$ taková, že algoritmus provede maximálně $k \cdot n^2$ instrukcí (například pro každé $n$ větší než 100 provede algoritmus maximálně $42 \cdot n^2$ instrukcí). Také si můžeme všimnout, že například algoritmus, který vždy provede $5 + 2n + 3n^4$ instrukcí běží v čase $\mathcal{O}(n^4)$, jelikož $5 + 2n + 3n^4 < 5n^4$ pro každé $n > 1$ (ze stejného důvodu bychom mohli tvrdit, že tentýž algoritmus běží v čase $\mathcal{O}(2^ n)$, tato informace by ale pro nás nebyla příliš cenná – vždy se snažíme o co nejtěsnější odhad.) O našem algoritmu na hledání čísla v poli tedy můžeme říct, že má časovou složitost $\mathcal{O}(n)$.

V předchozím textu jsme vám trochu zalhali. Náš algoritmus umíme drobně upravit tak, že pro něj půjde najít lepší odhad než $\mathcal{O}(n)$. Stačilo by po každém průchodu cyklem zkontrolovat, jestli už jsme číslo našli, a pokud ano, ukončit provádění smyčky. Pokud by tedy první z čísel v posloupnosti bylo 42, algoritmus by provedl jen konstantně mnoho instrukcí (počet instrukcí by byl nezávislý na $n$), běžel by tedy v čase $\mathcal{O}(1)$. Takový případ ale pro nás není příliš zajímavý, protože nikdy nevíme, jaká čísla na vstupu dostaneme, a nemůžeme se při návrhu algoritmů spoléhat na to, že budeme mít pokaždé štěstí. Pokud tedy není řečeno jinak, budeme vždy určovat časovou složitost v nejhorším případě. Budeme tedy předpokládat, že nepřítel nám zadal vstup tak, aby náš algoritmus běžel co nejdéle. Taky si to můžeme představit tak, že spustíme algoritmus pro všechny vstupy dané délky a budeme počítat ten vstup, na který jsme potřebovali nejvíce instrukcí. S touto definicí složitosti už tedy opravdu platí naše dřívější poznámka, že najít číslo v poli $n$ čísel obecně neumíme rychleji než v čase $\mathcal{O}(n)$.


Úloha 1 [2b]: Vymyslete algoritmus, který zjistí, kde se v poli nachází největší číslo a jaké číslo to je. Můžete předpokládat, že největší číslo je v poli jen jedno.


Tato úložka by měla jít vyřešit podobně jako ukázkový problém výše. Kdykoliv po vás chceme vymyslet algoritmus, rádi bychom slyšeli i jeho časovou složitost. To k algoritmu patří, protože to je v určitém slova smyslu to, co nám říká, jak je daný algoritmus dobrý.

Když už umíme najít maximum v poli, tak není těžké pole setřídit.


Úloha 2 [3b]: Vymyslete algoritmus, který setřídí pole čísel. Jinými slovy, chtěli bychom čísla seřadit podle jejich velikosti.


Tento problém se vám pravděpodobně nepodaří vyřešit v čase $\mathcal{O}(n)$. Pokud ano, určitě nám takové řešení pošlete. Jedná se totiž o slavný otevřený problém, který se informatici snaží vyřešit již po desetiletí. A pokud máte pomalejší řešení, také ho určitě pošlete, i když si myslíte, že by to mohlo jít rychleji.

Lze dokázat, že třídit nejde rychleji než v $\mathcal{O}(n \log n)$, ale tento důkaz předpokládá, že si zakážeme s čísly dělat cokoliv kromě porovnávání. Kdybyste tento důkaz viděli, tak si vzpomeňte na tento předpoklad, díky kterému si důkaz neprotiřečí s tím, že bychom chtěli umět třídit v čase $\mathcal{O}(n)$.


Bonusová verze [+2b]: Vyřešte ten samý problém, ale jen s konstantní pamětí navíc. To znamená, že máte v paměti pole, chcete ho setřídit a smíte při tom využívat libovolné konstantní (tedy nezávislé na $n$) množství proměnných. Už si ale třeba nemůžete pořídit pole, do kterého budete ukládat setříděnou posloupnost. To konkrétně znamená, že setříděná čísla budou na konci muset být v poli, ve kterém jste je dostali (na výstup nic nevypisujte).


Na závěr formálněji popíšeme a odůvodníme chování našeho modelu. Pokud následující část nechcete číst, nijak vám to nebrání v řešení témátka, vážou se k ní ale některé další problémy.

Formální popis modelu

Náš počítač bude mít paměť, která se skládá z nekonečně mnoha paměťových buněk očíslovaných celými čísly (představujte si ji jako nekonečnou posloupnost čtverečků). V každé buňce může být uloženo libovolně velké celé číslo. Číslu buňky budeme říkat adresa. Buňka může být určena dvěma způsoby: Přímou adresací – napíšeme adresu buňky do hranatých závorek (buňku s adresou 3 tedy značíme [3]), nebo nepřímou adresací – do dvojitých hranatých závorek napíšeme adresu buňky, ve které je uložena výsledná adresa buňky (buňku, jejíž adresa je uložena v buňce s adresou 3, tedy značíme [[3]]).

Každý algoritmus, který chceme na našem počítači spustit, musíme zapsat pomocí instrukcí. Počítači tedy předáme seznam instrukcí (ekvivalent kódu napsaného v programovacím jazyce pro skutečné počítače) a do určených paměťových buněk napíšeme vstup. Na reálném počítači by vstup pocházel z nějakého souboru nebo by ho zadal uživatel, ale my budeme pro jednoduchost předpokládat, že ho už máme někde uložený. Počítač poté provede všechny instrukce v takovém pořadí, v jakém jsou zapsány. Až mu instrukce dojdou, skončí. Počítač navíc může pomocí instrukce print postupně vypisovat čísla na výstup. Výstupem je pak posloupnost čísel, které vypsal za dobu svého běhu.

Nyní již přímo k instrukcím našeho počítače. Typická instrukce bere dva argumenty – každý z nich je (přímo či nepřímo adresovaná) paměťová buňka, nebo celé číslo. Pokud je argumentem buňka, instrukce si vždy přečte číslo, které je v ní uložené, a dále počítá s ním. S takto určenými celými čísly instrukce něco provede a výsledek uloží do předem určené paměťové buňky.

Samotné instrukce budou následující:

  • Instrukce přiřazení $\gets $ bere jeden argument a jeho hodnotu uloží do určené buňky. Například [1] $\gets $ [2] přečte číslo z druhé paměťové buňky a uloží ho do první paměťové buňky.

  • Instrukce $+$, $-$, $\cdot $ a $/$ berou vždy dva argumenty, spočítají jejich součet, rozdíl, součin nebo podíl (zaokrouhlený dolů na celé číslo) a výsledek uloží do dané buňky. Například [[4]] $\gets $ [1] $+$ 2 vezme číslo uložené v první buňce, přičte k němu dvojku a výsledek uloží do buňky, jejíž adresa je uložena v buňce číslo 4.

  • Instrukce skoku nebere žádný argument, ale „skočí“ v našem programu na označené místo. Někam mezi instrukce tedy napíšeme klíčové slovo (třeba „bagr“). Pokud na jiném místě napíšeme instrukci „skok na bagr“, náš počítač začne provádět instrukce, které následují za slovem „bagr“. Můžeme tím tedy způsobit, že se některé instrukce přeskočí, nebo naopak provedou víckrát.

  • Instrukce podmíněného příkazu bere dva argumenty, podmínku, kterou mají splňovat, a libovolnou jinou instrukci s jejími argumenty. Podmínka je vždy některý z matematických operátorů ($<$, $>$, $\ge $, $\le $, $=$, $\neq $). Pokud je podmínka splněna, provede se daná instrukce. Např. „Pokud [1] $>$ 1, [2] $\gets $ 3“ uloží do druhé buňky číslo 3, pokud je v první buňce uloženo číslo větší než 1.

  • Instrukce print vypíše argument na výstup.

Tím je náš model kompletní.

Model jsme se snažili zavést tak, aby byl co nejjednodušší, ale zároveň uměl spočítat vše, co umí dnešní počítače, a to se stejnou časovou složitostí. Výhodou našeho nového modelu je, že má méně instrukcí a lépe se s ním pracuje matematicky (třeba se v něm lépe dokazuje, že problém nelze algoritmicky vyřešit), zatímco v tom předchozím se zase lépe uvažuje o programech. Můžete si zkusit rozmyslet, že ve skutečnosti není o nic slabší než náš dříve zavedený uživatelsky přívětivější model…


Problém: Zkuste dokázat, že jakýkoliv program, který funguje na modelu, který jsme si pro větší pohodlnost dříve zavedli, lze přepsat tak, aby fungoval i na tomto minimalistickém modelu se stejnou časovou složitostí. Můžete to samozřejmě dokázat jen pro nějakou část – například vysvětlit, jak v minimalistickém modelu vytvořit pole, podmínku či cyklus.


Možná vám přijde zvláštní, že jsme schopni na našem modelu počítat s libovolně velkými čísly v konstantním čase. Říkáte si, že to asi neodpovídá realitě, protože určitě bude existovat vážně velké číslo, které na opravdový počítač ani nepůjde uložit, natož aby s ním počítače uměly pracovat v konstantním čase (ať už to u reálných počítačů znamená cokoliv). Nám to také přijde zvláštní. Je na vás, abyste tento problém vyřešili. Zkuste náš model nebo způsob počítání složitosti nějak upravit, nebo si vymyslet vlastní výpočetní model a počítat časovou složitost na něm. Můžete samozřejmě popsat více různých možností.


Problém: Navrhněte výpočetní model nebo způsob počítání časové složitosti, který bude odpovídat realitě v tom, že operace s dlouhými čísly trvají déle než s krátkými.


Ptáte se, zda je to opravdu třeba? Zatím jsme si neukázali žádný způsob, jak by šlo konstantní operace s dlouhými čísly zneužít. Jedním z problémů, při jehož řešení to jde, je například již zmíněné třídění čísel, které lze v našem modelu provést v $\mathcal{O}(n)$, a tedy není tak úplně pravda, že by to byl slavný otevřený problém, jak jsme psali. Ale v libovolném rozumném modelu tomu tak je. Další takový problém je násobení matic, které lze zrychlit tím, že zakódujeme $n$ čísel do jednoho a poté umíme provést aritmetickou operaci na $n$ číslech v čase $\mathcal{O}(1)$. Tyto konstrukce však nejsou úplně jednoduché, a nebudeme je zde tedy ukazovat. Pilný řešitel si je může vymyslet sám a pak o tom napsat pro ostatní.


Těžký problém: Vymyslete nějaký algoritmus, který zneužívá operace s dlouhými čísly v konstantním čase. (Řešení tohoto problému nebudeme zveřejňovat, bude tedy možnost posílat k němu řešení po celý školní rok.)


Kuba a Tom; domestomas+mam@gmail.com
e-mailová konference: algoritmy@mam.mff.cuni.cz


1) AND a OR jsou logické spojky, které jste pravděpodobně brali ve škole v rámci výrokové logiky pod názvy konjunkce a disjunkce. Složený výrok se spojkou AND je pravdivý právě tehdy, když jsou pravdivé oba výroky, a se spojkou OR právě tehdy, když je pravdivý alespoň jeden z nich.

2) Přestože pojem „óčková notace“ nezní úplně odborně, anglicky se toto značení skutečně nazývá „Big O notation“.

3) Formální definici si můžete přečíst třeba na Wikipedii: https://en.wikipedia.org/wiki/Big_O_Notation