11. Efektivita algoritmov

  • Aké druhy efektivity rozlišujeme ?

Algoritmus – s algoritmami sa bežne stretávame v každodennom živote. V podstate je algoritmus presný návod na zvládnutie určitej činnosti. Počítačom musíme preložiť postup do ich reči, do série príkazov. Algoritmus v informatike charakterizujeme ako postup, ktorým získame zo vstupných údajov v konečnom počte krokov, a teda v určitom čase odpovedajúce (správne) výstupne údaje (výsledky).

Ak chceme, aby naše programy bežali rýchlo, či dokonca, aby sme sa dožili ich úspešného ukončenia, mali by sme dbať o ich efektivitu. Tá sa dá merať časovou a pamäťovou zložitosťou.

 

Časovú zložitosť algoritmu môžeme definovať ako závislosť časových nárokov algoritmu na veľkosti konkrétneho riešeného problému alebo konkrétnych vstupných údajov. Neudávame ju však v žiadnych bežných časových jednotkách, pretože skutočná doba výpočtu programu realizujúceho navrhnutý algoritmus závisí tiež na množstve čisto technických parametrov, ako je napríklad rýchlosť procesora použitého počítača, zatiaľ čo my chceme charakterizovať rýchlosť práce algoritmu samého. Budeme preto časovú zložitosť vyjadrovať počtom elementárnych operácií (aritmetických, logických, porovnaní apod.), ktoré budú vykonané pri výpočte algoritmu nad zvolenými vstupnými údajmi. Časová zložitosť algoritmu A je teda funkcia tA, ktorá každej hodnote N, charakterizujúcej veľkosť spracovávaných údajov, priraďuje hodnotu tA(N), čo je počet operácií, ktoré algoritmus A vykoná pri spracovaní údajov veľkosti N.

Je potrebné rozlišovať časovú zložitosť algoritmu v najhoršom prípade a časovú zložitosť v priemernom prípade. Časová zložitosť v najhoršom prípade je funkcia udávajúca pre každú hodnotu N ako najdlhšie môže trvať výpočet algoritmu s ľubovoľnými údajmi veľkosti N. Naproti tomu časová zložitosť v priemernom prípade nám hovorí, ako dlho bude algoritmu v priemere trvať spracovanie vstupných údajov veľkosti N. Nie je to teda už horný odhad, ale priemerná očakávaná doba výpočtu pre údaje veľkosti N, získaná na základe úvah o všetkých možných konkrétnych hodnotách vstupných údajov veľkosti N.

Pamäťovú zložitosť algoritmu definujeme obdobne ako závislosť pamäťových nárokov algoritmu na veľkosti riešeného problému. Vyjadrujeme ju ako počet premenných, resp. pamäťových miest, ktoré algoritmus pri výpočte so zvolenými vstupnými údajmi potrebuje. Pamäťová zložitosť algoritmu A je teda opäť istou funkciou mA, ktorá veľkosti vstupných údajov veľkosti N priraďuje potrebný počet pamäťových miest mA(N), ktoré bude algoritmus A pri výpočte s týmito údajmi využívať.

I keď sa obmedzíme iba na časovú a pamäťovú zložitosť algoritmov pri hľadaní toho najlepšieho, môžeme sa dostať do ťažkej situácie, pretože tieto dve kritériá často stoja proti sebe. Stáva sa totiž, že k zrýchleniu výpočtu musíme použiť nejakú pomocnú dátovú štruktúru slúžiacu k uchovávaniu vopred spočítaných a pripravených hodnôt. Najrýchlejší možný algoritmus riešiaci úlohu potom nie je optimálny z hľadiska pamäťových nárokov a naopak algoritmus s najmenšou pamäťovou zložitosťou zase nemusí byť najrýchlejší.

V súčasnej dobe sa obyčajne dáva prednosť časovému hľadisku a hľadajú sa čo najrýchlejšie algoritmy, a to i za cenu potreby dodatočnej pamäte.

  • Ako hodnotíme efektivitu algoritmov? Na konkrétnom príklade ukážte spôsob hodnotenia efektivity.

 

Každý správny programátor programátor by mal poznať nielen programovací jazyk, ale aj zásady pre tvorbu algoritmov. Tie by mali spĺňať šesť základných vlastností: elementárnosť, determinovanosť, rezultatívnosť, konečnosť, hromadnosť, efektívnosť.

Efektívnosť algoritmu

-určuje sa najmä vzhľadom na potrebný výpočtový čas a požadovanú kapacitu pamäti,

-efektívny algoritmus je taká postupnosť krokov, ktorá daný problém rieši s minimálnym počtom použitých prostriedkov v čo najkratšom čase.

Pri zložitých problémoch je efektívnosť algoritmu druhoradá – cieľom je zvyčajne vytvoriť akýkoľvek algoritmus, otestovať ho a až potom prípadne zvýšiť jeho efektivitu.

Aj algoritmus, ktorý nie je efektívny môže fungovať správne. Efektívnosť je preto skôr rozširujúcou vlastnosťou, ako podmienkou pre nevyhnutne správny postup. Efektívny algoritmus je taký, ktorý s použitím minimálneho počtu prostriedkov v čo najkratšom čase vyrieši daný problém.

Príklad: Vypočítajte súčet čísel od 1 do 100. Neefektívnym algoritmom by bolo postupné sčítavanie 1+2+…+99+100. Omnoho efektívnejším spôsobom by bol výpočet (1+100)*50.

  • Uveďte príklad, ktorý je možno riešiť pomocou pažravej metódy a uveďte riešenie.

 

Čo to  teda sú tie pažravé algoritmy?(Greedy algorithms) Ak riešime úlohu pažravo, znamená to, že v každej situácii sa snažíme nájsť najlepšie možné riešenie a dúfame, že výsledné riešenie bude tiež najlepšie možné. Takýto postup je prirodzený, lebo väčšina ľudí sa správa pažravo „od prírody“, či už pre uspokojenie svojich potrieb alebo potrieb rodiny. Ak však chceme nachádzať optimálne riešenia, musíme si dávať pozor na to, či pažravá stratégia dáva naozaj optimálne riešenie pre konkrétnu úlohu.

Príklad:

Greedy algoritmus – Vyplatenie mincí v banke.  (V úlohe o minciach vždy použijeme najväčšiu možnú mincu.)

Potrebujem vyplatiť 49 Sk pomocou čo najmenšieho počtu bankoviek a mincí.

  1. Zoberiem lokálne maximum (v našom prípade 20 Sk, pretože je to najväčšia použiteľná bankovka), čiže 49 – 20 = 29, použité = [dvadsať korún]
  2. 29 – 20 = 9, použité = [dvadsať korún, dvadsať korún]
  3. 9 – 5 = 4, použité = [dvadsať korún, dvadsať korún, päť korún]
  4. 4 – 2 = 2, použité = [dvadsať korún, dvadsať korún, päť korún, dve koruny]
  5. 2 – 2 = 0, použité = [dvadsať korún, dvadsať korún, päť korún, dve koruny, dve koruny]

Pomocou greedy algoritmu som na základe lokálne najoptimalnejšieho riešenia našiel riešenie celkového problému. 49 Sk vyplatím použitím bankoviek a mincí [dvadsať korún, dvadsať korún, päť korún, dve koruny, dve koruny], pričom je to najmenší možný počet.

Kontrapríklad:

Predstavme si situáciu, kde máme iba mince 1, 4, 5 a chcem rozmeniť 8 korún na najmenej mincí (modelová situácia). Greedy algorimus v prvom kroku zoberie najväčšiu použiteľnú mincu, t.j. 5. V ďalšom kroku mu ostáva použiť uz iba mincu 1. Čiže výsledne riešenie pomocou greedy algoritmu bude v tvare [päť korún, jedna koruna, jedna koruna, jedna koruna]. Toto riešenie ale nieje optimálne. Optimálne riešenie je [štyri koruny, štyri koruny].

Reklamy

One thought on “11. Efektivita algoritmov

Pridaj komentár

Zadajte svoje údaje, alebo kliknite na ikonu pre prihlásenie:

WordPress.com Logo

Na komentovanie používate váš WordPress.com účet. Odhlásiť sa / Zmeniť )

Twitter picture

Na komentovanie používate váš Twitter účet. Odhlásiť sa / Zmeniť )

Facebook photo

Na komentovanie používate váš Facebook účet. Odhlásiť sa / Zmeniť )

Google+ photo

Na komentovanie používate váš Google+ účet. Odhlásiť sa / Zmeniť )

Connecting to %s