Třídicí číslo - Sorting number

V matematice a informatice je třídění čísel jsou posloupností čísel zavedených v roce 1950 Hugo Steinhaus pro analýzu porovnání řazení algoritmy. Tato čísla udávají nejhorší počet srovnání použitých oběma binární vložení řazení a Sloučit třídění. Existují však i jiné algoritmy, které používají méně srovnání.

Vzorec a příklady

The ${ displaystyle n}$toto třídicí číslo je dáno vzorcem^[1]

${ displaystyle n , S (n) -2 ^ {S (n)} + 1}$

kde

${ displaystyle S (n) = lpodlaha 1+ log _ {2} n rpodlaha.}$

Pořadí čísel daných tímto vzorcem (počínaje ${ displaystyle n = 1}$) je

0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, ... (sekvence A001855 v OEIS ).

Stejnou posloupnost čísel lze také získat z relace opakování^[2]

${ displaystyle A (n) = A { bigl (} lfloor n / 2 rfloor { bigr)} + ​​A { bigl (} lceil n / 2 rceil { bigr)} + ​​n-1. }$

Je to příklad a 2-pravidelná sekvence.^[2]

Asymptoticky, hodnota ${ displaystyle n}$toto třídicí číslo kolísá mezi${ displaystyle n log _ {2} n-n}$a${ displaystyle n log _ {2} n-0,915n}$v závislosti na poměru mezi ${ displaystyle n}$ a nejbližší síla dvou.^[2]

Aplikace na třídění

V roce 1950 Hugo Steinhaus zjistil, že tato čísla počítají počet srovnání použitých binární vložení řazení, a domnívali se (nesprávně), že poskytují minimální počet srovnání potřebných k řazení ${ displaystyle n}$ položky pomocí libovolného porovnání řazení. Domněnku vyvrátil v roce 1959 L. R. Ford Jr. a Selmer M. Johnson, který našel jiný třídicí algoritmus, Ford-Johnson sloučit-vložit řazení, používající méně srovnání.^[1]

Stejná posloupnost třídění čísel také dává nejhorší případ počet srovnání použitých Sloučit třídění seřadit ${ displaystyle n}$ položky.^[2]

Další aplikace

Třídicí čísla (posunutá o jednu pozici) také dávají velikosti nejkratší možné supervzorky pro vrstvené permutace.^[3]

Reference