» 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

Jak funguje největší akumulátor v Česku: podívejte se do elektrárny Dlouhé Stráně

Jak funguje největší akumulátor v Česku: podívejte se do elektrárny Dlouhé Stráně

** Přečerpávací vodní elektrárna Dlouhé stráně je obdivuhodné technické dílo ** Stejná turbína vyrábí elektřinu i tlačí vodu zpět do horního jezera ** Strojovna elektrárny je zabudována v podzemí

David Polesný | 35

Google Cloud Next: Blíží se bitva o to, kdo ovládne cloud, tedy internet zítřka

Google Cloud Next: Blíží se bitva o to, kdo ovládne cloud, tedy internet zítřka

** Google v týdnu ukázal nové telefony Pixel ** V Londýně se ale také konal Google Cloud Next ** Konference o tom, jak bude vypadat internet v cloudu zítra

Jakub Čížek | 31

Porno insider: Jak virtuální realita vstupuje do filmů pro dospělé

Porno insider: Jak virtuální realita vstupuje do filmů pro dospělé

** Pornografie údajně představuje třetinu internetové obsahu a je technologický tahounem ** Do erotického obsahu postupně zasahuje i virtuální realita ** Kromě vizuálního vjemu se pracuje také na virtuálním uspokojení toho hmatového

Jan Dudek | 29

Photolemur 3: Prostě do něj přetáhnete fotky a začne se dít magie. Tedy údajně...

Photolemur 3: Prostě do něj přetáhnete fotky a začne se dít magie. Tedy údajně...

** Je lepší nabušený Photoshop, nebo program s jedním tlačítkem? ** Photolemur si myslí to druhé ** Tento fotoeditor neumí skoro nic, a přitom (skoro) všechno

Jakub Čížek | 19

Kde se bere elektřina v zásuvce? Poznejte 10 tajemství venkovních stožárů s dráty

Kde se bere elektřina v zásuvce? Poznejte 10 tajemství venkovních stožárů s dráty

Elektřina se vyrábí v elektrárnách, ale do zásuvek v našich domovech to pak má ještě hodně daleko. Dnes se na tuhle dlouhou cestu podíváme.

David Polesný | 82

Na Zemi je nejtepleji za posledních více než 100 tisíc let. Co nám hrozí?

Na Zemi je nejtepleji za posledních více než 100 tisíc let. Co nám hrozí?

** Letošní červenec byl třetím nejteplejším měsícem od roku 1880 ** Teplota naší planety roste raketovým tempem ** Co lidstvu hrozí v období, které v minulosti nemá obdoby?

Karel Kilián | 70


Aktuální číslo časopisu Computer

Jak vytvořit a spravovat vlastní web

Velký test herních klávesnic a DVB-T2 tunerů

Vše o formátu RAW

Vybíráme nejlepší základní desku