Analýza algoritmů
Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka
ATCZ62 - CLIL jako výuková strategie na vysoké škole
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

Analýza algoritmů
•Experimentální
•Reálná časová náročnost
•Teoretická
•Pseudo-code
•Počítání primitivních operací
•Asymptotická notace
•Asymptotická analýza
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

Experimentální analýza časové náročnosti
•Časová náročnost se liší podle množství vstupů a roste s velikostí vstupů
•Těžko se určuje průměrný případ
•Zaměřujeme se na nejhorší možný případ
•Lehce se analyzuje
•Kritický pro různé aplikace
•Hry, finance, robotika, automatické operace…
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

Experimentální analýza časové náročnosti
•Měření probíhá v prostředí, kde běží program (algoritmus)
•Nutnost implementovat algoritmus
•Může být obtížné
•Vyžaduje další znalosti
•Běh závisí na vstupech a jejich složení
•Ne všechny vstupy jsou zahrnuty v každém běhu
•Pro porovnání dvou algoritmů nutnost mít stejný hardware i software (stejné spuštěné programy,
stejné obsazení paměti…)
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

Teoretická analýza
•Používá popis pomocí operací místo konkrétní implementace
•Bere do úvahy všechny vstupy
•Umožňuje ohodnotit rychlost algoritmu nezávisle na hardware / software
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

Teoretická analýza – Pseudo-code
•Vyšší úroveň popisu algoritmu
•Více strukturovaný než klasicky popis
•Méně detailní než implementace
•Preferovaný zápis pro popis algoritmu
•Skrývá problémy konkrétní implementace
•
Algorithm arrayMax(A, n)
Input pole A o n celých číslech
Output největší prvek A
currentMax ¬ A[0]
for i ¬ 1 to n - 1 do
if A[i] > currentMax then
currentMax ¬ A[i]
return currentMax
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

Teoretická analýza – Pseudo-code
•Řízení běhu:
•If … then … else
•While … do
•Repeat … until
•For … do
•Hlavička metody (procedury, algoritmu)
•Algorithm Název (Arg1, Arg2,…)
•Input
•Output
•Volání metody (procedury, algoritmu)
•var.Název(Arg1, Arg2,…)
•Návrat hodnoty
•return Výraz
•Výrazy
• ← Přiřazení
• = Rovnost
• +, -, n2 ,… Matematické operace
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

Teoretická analýza – Primitivní operace
•Primitivní operace
•Základní operace provedená algoritmem
•Identifikovatelná v pseudokódu
•Nezávislá na programovacím jazyku
•Měla by být přesně definovaná
•Příklady:
•Vyhodnocení výrazu
•Přiřazení hodnoty do proměnné
•Indexování v poli
•Volání, návrat z metody (procedury, algoritmu)
•
Rectangle: Click to edit Master text styles Second level Third level Fourth level Fifth level
•Algorithm arrayMax(A, n) Počet operací
• currentMax ¬ A[0] 2
• for i ¬ 1 to n - 1 do 2 + n
• if A[i] > currentMax then 2(n - 1)
• currentMax ¬ A[i] 2(n - 1)
• { increment counter i } 2(n - 1)
• return currentMax 1
• Total 7n - 1
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

Teoretická analýza – Asymptotická notace
Notace (zápis)
Název
Příklad
O(1)
Konstantní
Určení sudého/lichého čísla
O(log n)
Logaritmická
Binární třídění pole
O(n)
Lineární
Hledání v netříděném seznamu
O(nlog n)
Log-lineární
FFT, merge sort
O(n2)
Kvadratická
Bubble sort, hranice pro quicksort
O(cn), pro c>1
Exponenciální
Problém obchodního cestujícího
O(n!)
Faktoriální
Problém obchodního cestujícího
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

Teoretická analýza – Asymptotická analýza
•Určujeme časovou náročnost algoritmu pomocí big O notace
•Nalezneme největší možný počet primitivních operací
•Vyjádříme je pomocí big O notace
•Konstanty a výrazy nižšího řádu, lze zanedbat při počítání primitivních operací
•Příklad:
•Určili jsme, že algoritmus  arrayMax provede maximálně 7n - 1 primitivních operací
•Řekneme, že pro časovou náročnost algoritmu arrayMax platí: O(n)
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich