On 2012-10-13, bartekltg <b...@g...com> wrote:
> Co daje 2^62 możliwych wyników - gałęzi algorytmu.

Niestety nie wiem co nazywasz "gałęzią algorytmu".
Drzewo decyzyjne ma unikatowe liście, czyli jest ich 20!.

> Jeśli zamieniasz elementy miejscami by zmniejszyć tą
> ilość, już wykonujesz niepotrzebne operacje.

W drzewku decyzyjnym nie ma niepotrzebnych operacji. Na tym polega
ta idea. Chyba nie łapiesz o czym piszę :).

> Dla 20 można taki algorytm napisać, ale jest on chyba
> dość teoretycznym tworem.
> Dla 4 i 5 to się takie rzeczy pisało, ale dla 20...

Teretycznym nie, bo ktoś to już napisał (istnieją wyniki).
Nie mniej w tym algorytmie nie chodzi o optymalizację, tylko
o wyznaczenie dolnego ograniczenia. Poza tym o tę głównie o tę
ideę są oparte sorty sprzętowe (dla tych, którzy nie chcą tracić
czasu na niepotrzebne operacje komputerów :)).

Zresztą istnieje algorytm (Ford & Johnson Merge-Insertion Sort),
który dla małych n jest bliski optymalnemu (i tym samym jest
zapewne najlepszym algorytmem dla krótkich ciągów). Dla n=20
akurat jest optymalny. Polecam poszukać, bo to naprawdę nieźle
wyrzeźbiona rzecz :).

pozdrawiam,
PK