Cvičení 4 - Analýza složitosti algoritmů

• Asymptotická složitost
• Notace Big-O, Big Omega, Big Theta
• Vizualizace tříd složitosti
• Hezká tabulka s komentářem
• Porovnání rychlosti růstu funkci výpočtem limity
• Dva jednoduché příklady

    MatrixMultiplication(A[0..n − 1, 0..n − 1], B[0..n − 1, 0..n − 1])
        //Multiplies two square matrices of order n by the definition-based algorithm
        //Input: Two n × n matrices A and B
        //Output: Matrix C = AB
        for i ← 0 to n − 1 do
            for j ← 0 to n − 1 do
                C[i, j] ← 0.0
                for k ← 0 to n − 1 do
                    C[i,j] ← C[i,j] + A[i,k] * B[k,j]
        return C

    Enigma(A[0..n − 1, 0..n − 1])
        //Input: A matrix A[0..n − 1, 0..n − 1] of real numbers
        for i ← 0 to n − 2 do
            for j ← i + 1 to n − 1 do
                if A[i,j] ≠ A[j,i]
                    return false
        return true

    

• Co tento algoritmus počítá ?
• Která operace je základní?
• Kolikrát se základní operace provede? Je třeba rozlišovat mezi nejlepším, nejhorším a průměrným případem?
• Jaká je třída složitosti algoritmu?
• Implementujte pseudokódy v jazyce C++, využijte šablonu dostupnou níže.
• Jednoduchou úpravou funkce fill vytvořte funkci fill2, abychom mohli otestovat čas běhu funkce Enigma v nejhorším případě.
• Otestujte dobu běhu algoritmu pro vyšší n (100, 200, 400, 800, 1600, 3200), dobu běhu programu pro danou velikost vstupu zapište do tabulky excelu. Případně můžete provést všechna měření najednou a vytisknout tabulku na standardní výstup.
• Pokud měření doby běhu programu v milisekundách vypíše nulu, měřte v mikrosekundách. V souboru níže je ukázka měření doby běhu algoritmu v obou jednotkách.
• Když zvetšíme vstup dvakrát, kolikrát by se měla prodloužit délka běhu implementovaných algoritmů? Nahlédnutím do vytvořené tabulky ověřte, zdali tento předpoklad platí.