NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
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
 
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
 
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
 
Nahoru Odpovědět
29.12.2013 17:53
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na hurvajs
David Hartinger: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
New kid back on the block with a R.I.P
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
Tvůrce
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.