1. Nechť v následujícím fragmentu programu je t čas vykonání metody vykonej( ). Ostatní časy zanedbáme. Odvoďte čas výpočtu programu T v závislosti na n a t v nejhorším případě.
for (i=n-1; i>=1; i--)
for (j=0; j<=i-1; j++)
if (a[j]>a[j+1])
vykonej();
Dosaďte t=2 a vyjádřete odvozený čas T jako funkci n. Dokažte asymptotickou složitost Θ(n2) pro T(n).
2. Nechť v následujícím fragmentu programu je t1 čas vykonání metody vykonej1( ) a t2 čas vykonání metody vykonej2( ). Ostatní časy zanedbáme. Odvoďte čas výpočtu T programu v závislosti na n, t1, t2.
for (i=0; i<=2*n-1; i++)
vykonej1();
for (i=0; i<=n-1; i++)
for (j=0; j<=i; j++)
vykonej2();
Dosaďte t1=1, t2=2 a vyjádřete odvozený čas T jako funkci n. Dokažte asymptotickou složitost Θ(n2) pro T(n).
Napište si definici, zvolte n0 a najděte hodnoty zbývajících konstant.