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
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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 18. 05. 2018 15:02 — Editoval Anonymystik (18. 05. 2018 15:06)

Anonymystik
Příspěvky: 533
Reputace:   45 
 

Minimální počet porovnání

Zdravím, rád bych se zeptal, zda podobný problém už někde byl vyřešený.

Uvažme, že máme na vstupu N libovolných různých reálných proměnných a chceme je seřadit podle velikosti. Kolik nejméně porovnání při tom musíme provést, abychom si byli jistí, že nám informace stačí k úplnému seřazení? (porovnáním rozumíme operaci, do níž vložíme dvě proměnné a na výstupu dostaneme větší z nich).

Nad problémem jsem se zamýšlel v souvislosti se sportovními turnaji. Představme si, že máme N různých soutěžících, kteří se navzájem poměřují v zápasech duelového typu. Předpokládejme, že tato množina soutěžících tvoří lineární uspořádání - lze je tedy v absolutním slova smyslu seřadit od nejlepšího po nejhoršího. Kolik musí odehrát zápasů, aby se dalo určit celkové pořadí?

Někoho by možná napadlo, že stačí N-1 porovnání, protože a_1 < a_2 < ... < a_N, mám zde N-1 nerovností a ty mi postačí. Jenže to bych musel přesně vědět, které proměnné porovnávat, což a-priori nevím. Například pro 3 soutěžící a, b, c bych mohl zjistit, že a<b, b>c ... takže vím, že b je nejlepší, ale stále odtud nevím, zda je lepší a nebo c.

Pro algoritmus merge-sort (pracující se složitostí O(N*log(N)) mi vyšlo, že počet porovnání pro N=2^k je maximálně N*log2(N) - N + 1. Tento algoritmus má nejlepší možnou asymptotickou složitost, ale to neznamená, že je nutně nejlepší ze všech.


"Do you love your math more than me?"   "Of course not, dear - I love you much more."   "Then prove it!"   "OK... Let R be the set of all lovable objects..."

Offline

 

#2 25. 05. 2018 22:01

check_drummer
Příspěvky: 2528
Reputace:   65 
 

Re: Minimální počet porovnání

↑ Anonymystik:
Ahoj, myslím, že to vyřešeno je:
Mějme algoritmus, který provádí tato provnávání, ten nám určuje binární strom (uzlem je vždy dané provnání a větve z něj vedou vlevo dolů a vpravo dolů v závislosti na tom, jak to porovnání dopadlo). Každý list takového stromu označme permuací, která nám říká, jak jsou dané prvky na začátku seřazeny. (Strom musí mít takový tvar, aby bylo možné listu přiřadit permutaci jednoznačně - jinak ten algoritmus není korektní.) Aby byl algoritmus korektní, musí se v listech toho stromu nacházet každá permutace alespoň jednou. Těch permutací je N! a na základě toho již lze odhadnout délku nějvětší větve toho stromu (stačí búno předpokládat, že mají všechny listy stejnou hloubku) - to je chování v nejhorším případě. A vyjde O(n.log(n)).

Napsal jsem to poněkud zrychleně, ale snad je ta myšlenka jasná.


Nikdy nechibuji.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson