Úvodní znalosti
Čas výpočtu
 Vytisknout studijní materiál

Zadání:

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).

Tipy pro řešení:

Napište si definici, zvolte n0 a najděte hodnoty zbývajících konstant.