More actions
Bez shrnutí editace |
Bez shrnutí editace |
||
| (8 medziľahlých úprav od rovnakého používateľa nie je zobrazených.) | |||
| Riadok 4: | Riadok 4: | ||
== Výpočtová zložitosť == | == Výpočtová zložitosť == | ||
{{Pojem|obsah=výpočtová zložitosť}} | |||
Každý program alebo algoritmus potrebuje určité množstvo výpočtových zdrojov – hlavne čas a pamäť. Keď riešime nejaký problém, často existuje viacero algoritmov, ktoré vedú k rovnakému výsledku, ale niektoré sú výrazne rýchlejšie ako iné. Ak chceme, aby náš program bežal efektívne aj pre veľké vstupy, potrebujeme pochopiť, ako sa jeho výkon mení so zväčšujúcim sa množstvom dát. A pretože objem dát sa v programovaní dá najľahšie vysvetliť pomocou množín, vyučovanie výpočtovej zložitosti obsahuje skoro vždy iba množiny a cykly. | Každý program alebo algoritmus potrebuje určité množstvo výpočtových zdrojov – hlavne čas a pamäť. Keď riešime nejaký problém, často existuje viacero algoritmov, ktoré vedú k rovnakému výsledku, ale niektoré sú výrazne rýchlejšie ako iné. Ak chceme, aby náš program bežal efektívne aj pre veľké vstupy, potrebujeme pochopiť, ako sa jeho výkon mení so zväčšujúcim sa množstvom dát. A pretože objem dát sa v programovaní dá najľahšie vysvetliť pomocou množín, vyučovanie výpočtovej zložitosti obsahuje skoro vždy iba množiny a cykly. | ||
=== Základné pojmy === | === Základné pojmy === | ||
{{Pojem|obsah=časová zložitosť, pamäťová zložitosť, najlepší, priemerný a najhorší prípad}} | |||
Predtým ako sa pustíme do konkrétneho algoritmu, si najskôr musíme stanoviť niekoľko základných pojmov: | Predtým ako sa pustíme do konkrétneho algoritmu, si najskôr musíme stanoviť niekoľko základných pojmov: | ||
| Riadok 12: | Riadok 14: | ||
* '''Pamäťová zložitosť''' – koľko pamäte potrebuje algoritmus počas behu; | * '''Pamäťová zložitosť''' – koľko pamäte potrebuje algoritmus počas behu; | ||
* '''Najhorší, priemerný''' a '''najlepší prípad''' – hodnotíme algoritmus nielen pre optimálne podmienky, ale aj pre tie najhoršie možné situácie; | * '''Najhorší, priemerný''' a '''najlepší prípad''' – hodnotíme algoritmus nielen pre optimálne podmienky, ale aj pre tie najhoršie možné situácie; | ||
{{Pojem|obsah=asymptotická notácia, triedy zložitosti}} | |||
Medzi ďalšie dva dôležité pojmy patria: | Medzi ďalšie dva dôležité pojmy patria: | ||
# '''[[Asymptotická notácia]]''': používa sa označenie <math display="inline">O(f(n))</math> (tzv. „''Big-O''“ notácia), ktoré vyjadruje ako sa výkon algoritmu mení | # '''[[Asymptotická notácia]]''': používa sa označenie <math display="inline">O(f(n))</math> (tzv. „''Big-O''“ notácia), ktoré vyjadruje ako sa výkon algoritmu mení so zväčšujúcim sa vstupom <math display="inline">n</math>; | ||
# '''Triedy zložitosti''': napríklad, existuje trieda '''P''' (predstavuje všetky problémy, ktoré vieme riešiť efektívne) a '''NP''' (problémy, ktoré vieme overiť rýchlo, ale ich riešenie môže byť veľmi pomalé); | # '''[[Triedy zložitosti algoritmických problémov|Triedy zložitosti]]''': napríklad, existuje trieda '''P''' (predstavuje všetky problémy, ktoré vieme riešiť efektívne) a '''NP''' (problémy, ktoré vieme overiť rýchlo, ale ich riešenie môže byť veľmi pomalé); | ||
{{Téma|Oblast=Kategória: | {{Téma | ||
[[Kategória: | | Oblast = Kategória:Algoritmy a výpočtová zložitosť | ||
| Poradie = 10 | |||
}}{{PojemConfig | |||
| nadradene_cislo = 1 | |||
}} | |||
[[Kategória:Algoritmy a výpočtová zložitosť]] | |||
Aktuálna revízia z 06:25, 6. máj 2025
Čo je výpočtová zložitosť a prečo je dôležitá?
Výpočtová zložitosť
Každý program alebo algoritmus potrebuje určité množstvo výpočtových zdrojov – hlavne čas a pamäť. Keď riešime nejaký problém, často existuje viacero algoritmov, ktoré vedú k rovnakému výsledku, ale niektoré sú výrazne rýchlejšie ako iné. Ak chceme, aby náš program bežal efektívne aj pre veľké vstupy, potrebujeme pochopiť, ako sa jeho výkon mení so zväčšujúcim sa množstvom dát. A pretože objem dát sa v programovaní dá najľahšie vysvetliť pomocou množín, vyučovanie výpočtovej zložitosti obsahuje skoro vždy iba množiny a cykly.
Základné pojmy
Predtým ako sa pustíme do konkrétneho algoritmu, si najskôr musíme stanoviť niekoľko základných pojmov:
- Časová zložitosť – hovorí nám, koľko operácií vykoná algoritmus v závislosti od veľkosti vstupu (označujeme ju často ako );
- Pamäťová zložitosť – koľko pamäte potrebuje algoritmus počas behu;
- Najhorší, priemerný a najlepší prípad – hodnotíme algoritmus nielen pre optimálne podmienky, ale aj pre tie najhoršie možné situácie;
Medzi ďalšie dva dôležité pojmy patria:
- Asymptotická notácia: používa sa označenie (tzv. „Big-O“ notácia), ktoré vyjadruje ako sa výkon algoritmu mení so zväčšujúcim sa vstupom ;
- Triedy zložitosti: napríklad, existuje trieda P (predstavuje všetky problémy, ktoré vieme riešiť efektívne) a NP (problémy, ktoré vieme overiť rýchlo, ale ich riešenie môže byť veľmi pomalé);