Matematické Fórum

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.