Dotaz: Časová složitost

[Elune]

Ahoj, dovedl by prosim někdo poradit s výpočtem časové složitosti? Konkrétně mám toto zadání.

"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). Pomůcka: Napište si definici, zvolte n0 a najděte hodnoty zbývajících konstant c1 a c2."

---

---

Odpovědi

[Elune]

Omlouvám se za formát, nějak se to rozhodilo, cykly jsou samozřejmě vnořené..

for (i=n-1; i>=1; i--){

for (j=0; j<=i-1; j++)

if (a[j]>a[j+1]){

vykonej();

}

}

}

[rastos]

Urob si malý program, ktorý ten kód vykoná pre rôzne 'n' a vypíše, koľko krát sa cyklus vykoná. Ten 'if' môžeš vyraziť a miesto vykonej(), daj len nejaké počítadlo.

[Jakub Lucký]

http://www.abclinuxu.cz/faq/aplikace/udelate-za-me-ukol

To neni dotaz, to je komplet zadani. Ano, nepochybne dovedeme poradit. S cim mas konkretne problem?