Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 19. 12. 2021 11:00

fmfiain
Příspěvky: 586
Reputace:   
 

Rozhodovací strom

Dobrý deň,
čítal som, že minimálna zložitosť Qsortu sa dá zistiť rozhodovacím stromom (jedná sa o obyčajné porovnanie dvoch a viac prvkov). Viem ako rozhodovací strom vyzerá, ale neviem ako z neho vyčítať tú minimálnu zložitosť.

Ďakujem za odpoveď a ochotu.

Offline

 

#2 19. 12. 2021 11:04

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň,
práve som čítal, že tento rozhodovací strom, funguje rovnako pre všetky známe triediace algoritmy.

Ďakujem za odpoveď a ochotu.

Offline

 

#3 19. 12. 2021 11:25

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň,
na tejto stránke: http://www.kiwiki.info/index.php/Algori … Quick_sort
by to malo byť [mathjax]n*log(n)[/mathjax].
Ale ako sa k tomu dostali?

Ďakujem za odpoveď a ochotu.

Offline

 

#4 19. 12. 2021 17:46

check_drummer
Příspěvky: 3692
Reputace:   89 
 

Re: Rozhodovací strom

↑ fmfiain:
Ahoj, co to je minimální složitost?


Ve 21. století i vzdělaní lidé učili své děti, že látka je tvořená z atomů.

Online

 

#5 19. 12. 2021 17:47

check_drummer
Příspěvky: 3692
Reputace:   89 
 

Re: Rozhodovací strom

Jinak nedávno tu někdo řešil složitost QuickSortu v průměrném případě, je to ca týden, tak stačí zapátrat.


Ve 21. století i vzdělaní lidé učili své děti, že látka je tvořená z atomů.

Online

 

#6 20. 12. 2021 10:38 — Editoval fmfiain (20. 12. 2021 10:54)

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň ↑ check_drummer:,
minimálna zložitosť  je minimálna hĺbka rozhodovacieho stromu pre [mathjax]n \ge 2[/mathjax], kde n je počet porovnavanych čísel. V základe sa jedná o najkratšiu cestu od koreňa po list.
Problém je, že sa jedná o všeobecné  vyjadrenie tejto cesty pre n porovnávanych čísel.

Ďakujem za odpoveď a ochotu.

Offline

 

#7 20. 12. 2021 10:41

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň ↑ check_drummer:,
ten Qsort v priemernom prípade som tu riešil ja :).

Ďakujem za odpoveď a ochotu.

Offline

 

#8 20. 12. 2021 10:48

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň ↑ check_drummer:,
zložitosť triediaceho algoritmu sa meria počtom porovnaní
prvku s ostatnými prvkami.

Ďakujem za odpoveď a ochotu.

Offline

 

#9 20. 12. 2021 11:06 — Editoval fmfiain (20. 12. 2021 11:06)

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň ↑ check_drummer:,
ak je zložitosť n, tak to znamená, že stačí prejsť jeden krát n prvov a mám všetko utriedené.
Ak ale je zložitosť [mathjax]n\log_{}n[/mathjax], musím prejsť [mathjax]n\log_{}n[/mathjax] prvkov aby som mal všetko utriedené.
A to si neviem predstaviť.

Ďakujem za odpoveď a ochotu.

Offline

 

#10 20. 12. 2021 11:20

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň ↑ check_drummer:,
ak vytvoríme dva cikly, pričom jeden je vnoreny (napr. Buble sort)
, musíme prejsť n krát n prvkov, čiže máme porovnanie [mathjax]n*n[/mathjax] prvkov a teda zložitosť je [mathjax]n^{2}[/mathjax].
Ale ten [mathjax]n \log_{}n[/mathjax] si fakt neviem predstaviť.

Ďakujem za odpoveď a ochotu.

Offline

 

#11 20. 12. 2021 15:44

Aleš13
Příspěvky: 224
Reputace:   
 

Re: Rozhodovací strom

Složitost n log n znamená jen to, že se obvykle dosáhne setřídění již po log n průchodech vnějšího cyklu. Ale pro Quicksort je minimální složitost n, když se už při prvním průchodu zjistí, že data jsou již setříděná. Teda jestli si to dobře pamatuju, naposledy jsem o Quicksortu slyšel někdy v minulém tisíciletí, od té doby ho nepoužívám, protože je pomalý a složitý :D

Offline

 

#12 20. 12. 2021 16:03 Příspěvek uživatele Stýv byl skryt uživatelem Stýv. Důvod: OT

#13 20. 12. 2021 17:49

osman
Příspěvky: 99
Pozice: v.v.
Reputace:   
 

Re: Rozhodovací strom

Zdravím, doporučuji se podívat na
https://www.algoritmy.net/article/10/Quicksort


Hlavní je zápal, talent se dostaví!

Offline

 

#14 20. 12. 2021 20:09 Příspěvek uživatele Aleš13 byl skryt uživatelem Stýv. Důvod: OT

#15 20. 12. 2021 23:37 Příspěvek uživatele check_drummer byl skryt uživatelem Stýv. Důvod: OT

#16 21. 12. 2021 10:03 Příspěvek uživatele Stýv byl skryt uživatelem Stýv. Důvod: OT

#17 21. 12. 2021 10:30 — Editoval fmfiain (21. 12. 2021 10:39)

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň všetkým,
ja som našiel takýto pomer:
[mathjax]n! \le 2^{h} \Rightarrow h \ge \log_{2}n! \approx cn \log_{2} n[/mathjax]
Kde n! je permutacia čísel v listoch a h je hĺbka stromu.

Ďakujem za odpoveď a ochotu.

Offline

 

#18 21. 12. 2021 10:33

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň všetkým,
mohli by ste mi vysvetliť to posledné [mathjax]\approx [/mathjax]?

Ďakujem za odpoveď a ochotu.

Offline

 

#19 21. 12. 2021 10:50 Příspěvek uživatele Aleš13 byl skryt uživatelem Stýv. Důvod: OT

#20 21. 12. 2021 10:55 Příspěvek uživatele Aleš13 byl skryt uživatelem Stýv. Důvod: OT

#21 21. 12. 2021 12:34 Příspěvek uživatele Stýv byl skryt uživatelem Stýv. Důvod: OT

#22 21. 12. 2021 13:06 Příspěvek uživatele check_drummer byl skryt uživatelem Stýv. Důvod: OT

#23 21. 12. 2021 14:35 — Editoval Aleš13 (21. 12. 2021 16:23) Příspěvek uživatele Aleš13 byl skryt uživatelem Stýv. Důvod: OT

#24 21. 12. 2021 14:40 — Editoval Aleš13 (21. 12. 2021 14:41) Příspěvek uživatele Aleš13 byl skryt uživatelem Stýv. Důvod: OT

#25 21. 12. 2021 14:52 Příspěvek uživatele Stýv byl skryt uživatelem Stýv. Důvod: OT

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson