a) Formulujte Master Theorem.
b) Pomocí Master Theoremu odhadněte složitost v závislosti na parametru a:
T(n) = aT(n/3) + O(n^2)a) Definujte univerzální množinu hashovacích funkcí.
b) Popište konstrukci univerzální množiny hashovacích funkcí.Máte algoritmus na hledání minimální kostry grafu:
-> Vstup: souvislý G s ohodnocenými hranami
-> Dokud jsou v G cykly:
-> Z nějakého cyklu smažete jeho nejdražší hranu
-> Výstup: zbývající hrany
a) Dokažte, že výstupem je minimální kostra.
b) Navrhněte implementaci algoritmu a odvoďte časovou složitost.