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

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

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

#28 23. 12. 2021 10:30

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň všetkým,
je zaujímavé čítať vašu diskusiu, ale nikto sa zatiaľ neviadril koľko je [mathjax]n \log_{2}n[/mathjax] prvkov. Zatiaľ ste sa len viadrili, že zložitosť n je taká, že stačí prejsť jeden krát n prvkov a ak boli prvky dopredu usporiadané tak to zistí.
Vari ak sú prvky qsortu dopredu usporiadané, tak stačí prejsť [mathjax]n \log_{2}n[/mathjax] prvkov (ak mám byť presný, tak sa jedná o porovnavanie a nie o počet prvkov).

Ďakujem za odpoveď a ochotu.

Offline

 

#29 23. 12. 2021 17:51

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

Re: Rozhodovací strom

fmfiain napsal(a):

nikto sa zatiaľ neviadril koľko je [mathjax]n \log_{2}n[/mathjax] prvkov.

Jednak jsem tu otázku nikde výše nezachytil, a jednak moc nedává smysl, [mathjax]n \log_{2}n[/mathjax] prvků je prostě [mathjax]n \log_{2}n[/mathjax] prvků...


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

Offline

 

#30 23. 12. 2021 19:05

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

Re: Rozhodovací strom

Dá se to taky brát tak, že [mathjax]log_2 n[/mathjax] je počet bitů které potřebuješ k zapsání čísla [mathjax]n[/mathjax]. Prostě při každém průchodu rozpůlíš interval a takhle to vyjde (u quicksortu za ideálních podmínek při správně zvoleném rozhodovacím prvku).

Offline

 

#31 24. 12. 2021 10:54

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň všetkým,
mohli by ste mi vypísať ako idú jednotlivé zložitosti od najrýchlejšie po najpomalsiu.
Ja by som začal: [mathjax]c, n, log n, n^{c}, c^{n}, n! [/mathjax].
Kde c je konštanta a n je počet porovnavanych čísel.
Určite nie sú všetky a možno ani v správnom poradí.

Ešte by som si podotkol, že zložitosť triediacich algoritmov sa meria počtom porovnaní a nie počtom prvkov. Lebo len tak môže mať jeden algoritmus s rovnakým počtom prvkov rôzne zložitosti.
Teda algoritmus Qsort môže mať v najhoršom prípade [mathjax]n^{2}[/mathjax] porovnaní a v ostatných prípadoch [mathjax]n \log_{2}n[/mathjax] porovnaní.


Ďakujem za odpoveď a ochotu.

Offline

 

#32 24. 12. 2021 11:06

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

Re: Rozhodovací strom

Složitost se bere že je úměrná počtu porovnání a počet porovnání se vypočítá z počtu prvků. Ty vzorečky [mathjax]n^{2}[/mathjax], [mathjax]n \log_{2}n[/mathjax] apod. říkají, kolik porovnání ten který algoritmus potřebuje k setřídění souboru. Pak by byla k diskusi ještě ta konstanta úměrnosti, což jsem zkusil nadhodit v již smazaných OT příspěvcích :-) Jednotlivé složitosti si nech nakreslit Wolframem, příkaz plot, je to názornější než tady cokoliv psát.

Offline

 

#33 24. 12. 2021 11:08

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň všetkým,
na bubble sorte sa to najľahšie vysvetľuje:
Prejdeme jedným poľom a ak urobíme swap, tak si to zaznacime.
Ak máme poznačené swap, tak triedime znova. Ak nie skončili sme. Ak sme nemali ani raz poznačené swap, prešli sme poľom iba raz a teda zložitosť bola n. Ak sme prešli poľom viac krát, čo tiež zaznacime niekde bokom, zložitosť bola väčšia a to niekoľko krát n porovnaní, čo je zhora ohraničené [mathjax]n^{2}[/mathjax].

Ďakujem za odpoveď a ochotu.

Offline

 

#34 24. 12. 2021 11:18 — Editoval Aleš13 (24. 12. 2021 11:19)

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

Re: Rozhodovací strom

Ano, je to přesně takhle, vždycky je tam minimální a maximální složitost podle toho jak moc je soubor nesetříděný (ale ne vždycky se ta minimální od maximální musí lišit a ne vždycky je ta minimální rovná n). Tedy jestli jsem správně pochopil na co se ptáš :-)

Offline

 

#35 24. 12. 2021 11:21

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň ↑ Aleš13:,
mohol by si mi prosím napísať link na ten Wolfram.
Potreboval by som presný link, kde mi to vykresli tie funkcie.

Ďakujem za odpoveď a ochotu.

Offline

 

#37 24. 12. 2021 11:29

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň ↑ Aleš13:,
už som to našiel.

Ďakujem za odpoveď a ochotu.

Offline

 

#38 25. 12. 2021 00:42

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

Re: Rozhodovací strom

fmfiain napsal(a):

Teda algoritmus Qsort môže mať v najhoršom prípade [mathjax]n^{2}[/mathjax] porovnaní a v ostatných prípadoch [mathjax]n \log_{2}n[/mathjax] porovnaní.

Podle mě i "druhý nejhorší" případ bude potřebovat [mathjax]n^{2}[/mathjax] porovnaní.
Ale pokud jde o asymptotické chování, tak to bude podle mě mezi [mathjax]n \log_{2}n[/mathjax] a [mathjax]n^{2}[/mathjax], tedy to hledané minimum bude podle mě [mathjax]n \log_{2}n[/mathjax]. Ale nevím k čemu je takové minimum dobré. Pokud bychom např. nejdřív zkontrolovali, zda je posloupnost setříděná, a pokud by byla, tak skončíme, tak by to minimum bylo n. Nebo bychom mohli pustit několik průchodů bubble sortu (nějaký pevný počet, třeba 10), a pokud by se během těch průchodů nepodařilo posloupnost utřídit, tak bychom pustili QuickSort, a i v tomto případě by byla minimální složitost n. A i tady je na místě otázka, k čemu je taková minimální složitost dobrá.
V tomto případě bych řekl, že je to spíše zajímavá akademická otázka.


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

Offline

 

#39 25. 12. 2021 00:45

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

Re: Rozhodovací strom

↑ fmfiain:
Složitostí je nekonečně mnoho, např. n.log(n), n.log(n).log(n), n.log(n).log(n).log(n),... Ale většinou lze říci, která z nich je "větší" než jiná, nejlépe asi pomocí jejich poměru a jeho limity.


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

Offline

 

#40 25. 12. 2021 10:39

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň ↑ check_drummer:,
ako by si počítal limitu z #17: [mathjax]\lim \frac{log_2 (n!)}{cn*log_2(n)}[/mathjax]
alebo naopak: [mathjax]\lim \frac{cn*log_2(n)}{log_2 (n!)}[/mathjax].
Vôbec neviem k čomu smeruje n. A tak isto neviem, ktorá s týchto limít je ta správna.
O tom n viem iba to, že je z jednej strany ohraničené [mathjax]\ge 2[/mathjax] a z druhej strany je ohraničené [mathjax]\le \infty [/mathjax].

Ďakujem za odpoveď a ochotu.

Offline

 

#41 25. 12. 2021 10:49

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň ↑ check_drummer:,
výsledok limity by mal byť 1, lebo medzi funkciami platí: [mathjax]\approx [/mathjax].

Ďakujem za odpoveď a ochotu.

Offline

 

#42 25. 12. 2021 10:57

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň ↑ check_drummer:,
mňa napadla iba úprava: [mathjax]\lim \frac{log_2 (n!)}{cn*log_2(n)} = \lim \frac{log_2 (n!)}{log_2(n^{cn})} = 1                  [/mathjax], alebo [mathjax]\lim \frac{cn*log_2(n)}{log_2 (n!)} = \lim \frac{log_2(n^{cn})}{log_2 (n!)} = 1[/mathjax].

A keď nad tým tak rozmýšľam a výsledky limít sú rovnaké, je jedno, ktorú si vyberiem.

Ďakujem za odpoveď a ochotu.

Offline

 

#43 25. 12. 2021 19:50

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

Re: Rozhodovací strom

U složitosti tě zajímá chování pro velká n. Čistě prakticky, když třídíš pole o sto prvcích, je většinou dost jedno jestli použiješ bubble sort nebo quick sort, pro řádově 100000 prvků už je rozdíl, jestli se výpočet při zdvojnásobení délky pole prodlouží 4x (bubble sort) nebo cca 2x (quicksort), proto se mluví o asymptotické složitosti. Opět s dodatkem, že doufám, že odpovídám na to na co se ptáš :-)

Offline

 

#44 30. 12. 2021 11:19

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň ↑ Aleš13: a ↑ check_drummer:,
ak má zmysel rátať iba vysoké n, tak potom tá limita v #42 je pre [mathjax]\lim_{n\to\infty }[/mathjax].
Mám pravdu?

Ďakujem za odpoveď a ochotu.

Offline

 

#45 30. 12. 2021 12:30

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

Re: Rozhodovací strom

↑ fmfiain:
Ano, stručně řečeno, všechny limity v souvislosti se složitostí jsou pro n jdoucí k nekonečnu. To jsem bral jako samozřejmou znalost.


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

Offline

 

#46 30. 12. 2021 12:32

fmfiain
Příspěvky: 586
Reputace:   
 

Re: Rozhodovací strom

Dobrý deň všetkým,
skúste sa vžiť do situácie študenta: Príde záverečná skúška a Vy dostanete na skúške algoritmus, ktorý ste nikdy pred tým nevideli. Jediná pomôcka je, že poznáte iba týchto 5 zložitostí: [mathjax]n, n\log n, n^{2}, n^{3}, 2^{n}[/mathjax].
Ako by ste hľadali jeho minimálnu, priemernú a maximálnu zložitosť. Skúste aspoň slovný postup bod po bode.

Ďakujem za odpoveď a ochotu.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson