Avatar
hurvajs
Člen
Avatar
hurvajs:

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:

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:

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:

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
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
hurvajs
Člen
Avatar
hurvajs:

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:

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:

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.