» Poradna » Programy

Časová složitost

 |   |  Microsoft Windows 7 Firefox 19.0

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

Alan Turing: Genius, který matematicky stvořil počítač

Alan Turing: Genius, který matematicky stvořil počítač

Řešením matematického problému se dostal k modelu teoretického stroje, který nese jeho jméno a je základem logiky univerzálních počítačů.

Pavel Tronner | 56

Google ADT-2: Miniaturní krabička s Android TV 8.0, kterou si nikdy nekoupíte

Google ADT-2: Miniaturní krabička s Android TV 8.0, kterou si nikdy nekoupíte

** Dlouho se nevědělo, co to přesně má být ** Pak se s krabičkou Google pochlubil na I/O ** Do „Chromecastu“ vtěsnal celý Android TV

Jakub Čížek | 24

Apple dal do MacBooku procesor Core i9 a 4TB SSD. Ani se neptejte, co za to chce...

Apple dal do MacBooku procesor Core i9 a 4TB SSD. Ani se neptejte, co za to chce...

** Apple aktualizoval notebooky MacBook Pro, dostaly nový hardware ** Těšit se můžete na nové procesory a větší paměť ** Cena nejvybavenějšího modelu překročí 200 tisíc korun

Martin Miksa | 99

Sex a rozmnožování při mezihvězdné cestě: Kolik lidí je potřeba pro let k Proximě Centauri?

Sex a rozmnožování při mezihvězdné cestě: Kolik lidí je potřeba pro let k Proximě Centauri?

** Vědci spočítali, jak velká by musela být posádka pro vícegenerační let k nejbližší hvězdné soustavě ** Proxima Centauri se nachází 4,3 světelných let od nás ** Za současných technologií bychom k ní letěli 6300 let

Petr Kubala | 53

Šmírovačka kamerami Googlu: Koukněte se, co nového zachytily na Street View

Šmírovačka kamerami Googlu: Koukněte se, co nového zachytily na Street View

Google stále fotí celý svět do své služby Street View. A novodobou zábavou je hledat v mapách Googlu vtipné záběry. Podívejte se na výběr nejlepších!

redakce | 44

Apple: naše mapy budou nejlepší na světě. Tajně jsme na nich pracovali několik let

Apple: naše mapy budou nejlepší na světě. Tajně jsme na nich pracovali několik let

** Apple odhalil své plány na zcela nové mapy ** Několik let pracuje na nových mapách, které by měly předběhnout konkurenci ** Objeví se s příchodem iOS 12 pro vybrané státy

Karel Javůrek | 50


Aktuální číslo časopisu Computer

Velký test 18 bezdrátových sluchátek

Vše o přechodu na DVB-T2

Procesory AMD opět porážejí Intel

7 NVMe M.2 SSD v přímém souboji