Nauč se s námi víc. Využij 50% bonus na e-learningové kurzy.
Pouze tento týden sleva až 80 % na e-learning týkající se Javy

Diskuze: Časová složitost algoritmů

Aktivity (7)
Avatar
hurvajs
Člen
Avatar
hurvajs:29.12.2013 17:36

Zdraví,
nevím jestli se to tady už někde probíralo, ale nevím si rady vypočítáním časové složitosti algoritmů, ve skriptech je to vysvětleno tak, že to nechápu :(
např. dostanu pseudokod ss
Selection-Sort(A[0::n

Editováno 29.12.2013 17:39
 
Odpovědět
29.12.2013 17:36
Avatar
hurvajs
Člen
Avatar
hurvajs:29.12.2013 17:47

nevím proč, ale nešlo mi přiložit pseudokod, takže to celé hodím do code

Selection-Sort(A[0:n - 1])
1 for j <- 0 to n - 2
2 do iMin <-  j
3 for i <-  j + 1 to n - 1
4 do if A[i ] < A[iMin] then iMin <- i
5 t <-  A[j ]; A[j ] <-  A[iMin]; A[iMin] <-  t

následně si rozepíšu jednotlivé operace a vypočítám viz. obrázek
nevím jestli to dělá správně, popřípadě bych prosil o vysvětlení
Editováno 29.12.2013 17:50
 
Nahoru Odpovědět
29.12.2013 17:47
Avatar
hurvajs
Člen
Avatar
hurvajs:29.12.2013 17:53

Ještě ten obrázek

http://sdrv.ms/1di6GQT

Editováno 29.12.2013 17:55
 
Nahoru Odpovědět
29.12.2013 17:53
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na hurvajs
David Čápka:29.12.2013 17:56

Ona je to docela věda, ale většinou dostaneš pár cyklů, co něco dělají s nějakou kolekcí.Stačí se podívat kolikrát ty cykly jedou v nejhorším případě. V tomto případě máš cyklus co projede n prvků a v něm další cyklus co projede n prvků. Dohromady tedy n2. Něco jsem o tom tady na devbooku napsal, četl jsi to?

Nahoru Odpovědět
29.12.2013 17:56
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
hurvajs
Člen
Avatar
hurvajs:29.12.2013 18:05

Ano, četl, ale nějak jsem to nepochopil, u zkoušky mu vysvětlím, jak daný algoritmus funguje, ale tohle je pro mě "španělská vesnice"..

 
Nahoru Odpovědět
29.12.2013 18:05
Avatar
coells
Redaktor
Avatar
Odpovídá na hurvajs
coells:29.12.2013 18:07

U třídícího algoritmu tě zajímá počet porovnání prvků a počet prohození prvků.

  • porovnávání děláš na řádce 4 a ta se provede kolikrát pro pole A o velikosti n
n-1 + n-2 + n-3 + ... + 1 = n*(n-1)/2 = (n*n - n)/2 krát
  • prohazování děláš na řádce 5 a ta se provede kolikrát pro pole A o velikosti n
n-1 krát

Takže celkový počet operací je (n2 - n)/2 + n - 1
Po úpravě n2 / 2 + n / 2 - 1

Asymptotická složitost O(n2 / 2 + n / 2 - 1) = O(n2)

Pokud potřebuješ spočítat ještě amortizovanou složitost, pak si pro pole o velikosti n vezmi všechny permutace a pro jednotlivé případy spočítej počet porovnání a z nich aritmetický průměr. V tomhle případě je ale jasné, že to bude opět O( n2 )

 
Nahoru Odpovědět
29.12.2013 18:07
Avatar
hurvajs
Člen
Avatar
hurvajs:30.12.2013 19:11

Dneska jsem se teda díval na ostatní algority(Insert, Bubble, Merge, Heap, Qiuck - sort) a jestli jsem to správně pochopil, tak selection, bubble a insert se odůvodní/vypočítá tímto způsobem

U třídícího algoritmu tě zajímá počet porovnání prvků a počet prohození prvků.

- porovnávání děláš na řádce 4 a ta se provede kolikrát pro pole A o velikosti n

n-1 + n-2 + n-3 + ... + 1 = n*(n-1)/2 = (n*n - n)/2 krát
- prohazování děláš na řádce 5 a ta se provede kolikrát pro pole A o velikosti n

n-1 krát
Takže celkový počet operací je (n2 - n)/2 + n - 1
Po úpravě n2 / 2 + n / 2 - 1

Asymptotická složitost O(n2 / 2 + n / 2 - 1) = O(n2)

Pokud potřebuješ spočítat ještě amortizovanou složitost, pak si pro pole o velikosti n vezmi všechny permutace a pro jednotlivé případy spočítej počet porovnání a z nich aritmetický průměr. V tomhle případě je ale jasné, že to bude opět O( n2 )

ostatní jsou "vysvětlené ve skriptech"

 
Nahoru Odpovědět
30.12.2013 19:11
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 7 zpráv z 7.