» Poradna » Programy

Časová složitost

Odpovědět  |  Zobrazit bez stromu  |  Upozornit redakci  |  nových odpovědí: 1/1
 |   |  Microsoft Windows 7 Firefox 19.0  |  [89.102.128.---]

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 na otázku

 |   |  Microsoft Windows 7 Chrome 25.0.1364.97

Vnější cyklus proběhne N-1 krát.Vnitřní cyklus proběhne i/2 krát. Tj (N-1)/2 krát.Protože počítáme nejhorší případ, tak musíme počítat s tím, že ten if bude vždy splněný a tedy metoda vykonej se spustí vždy.Když to dáš dohromady a zanedbáš všechny konstanty, tak dostaneš N*N složitost, tj Θ(n na 2)

Souhlasím  |  Nesouhlasím  |  Odpovědět

Související témata: Složitost



Určitě si přečtěte


Jak fungují kryptoměny: Za oponou se odehrává perfektně organizovaný chaos

Jak fungují kryptoměny: Za oponou se odehrává perfektně organizovaný chaos

** Bitcoin letos trhal rekordy ** Zdaleka není sám, jsou tu i další kryptoměny ** Jak vlastně kyberpeníze v nitru fungují?

13.  12.  2017 | Jakub Čížek | 47

Pojďme programovat elektroniku: Vyzkoušíme linuxový počítač Omega2 za stokorunu

Pojďme programovat elektroniku: Vyzkoušíme linuxový počítač Omega2 za stokorunu

** Má velikost poštovní známky ** Stojí něco málo přes stovku ** A tvrdí o sobě, že je to nejmenší linuxový počítač

10.  12.  2017 | Jakub Čížek | 7