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