NOVINKA: Kurz Práca s umelou inteligenciou teraz už od 0 €. Staň sa žiadaným profesionálom. Zisti viac:
NOVINKA: Kurz kybernetickej bezpečnosti teraz už od 0 €. Staň sa žiadaným profesionálom. Zisti viac:
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

Editované
 
Odpovedať
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í
Editované
 
Hore Odpovedať
29.12.2013 17:47
Avatar
hurvajs
Člen
Avatar
hurvajs:29.12.2013 17:53

Ještě ten obrázek

http://sdrv.ms/1di6GQT

Editované
 
Hore Odpovedať
29.12.2013 17:53
Avatar
David Hartinger
Vlastník
Avatar
Odpovedá 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?

Hore Odpovedať
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"..

 
Hore Odpovedať
29.12.2013 18:05
Avatar
coells
Tvůrce
Avatar
Odpovedá 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 )

 
Hore Odpovedať
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"

 
Hore Odpovedať
30.12.2013 19:11
Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zobrazené 7 správy z 7.