W dniu 2012-10-14 01:16, PK pisze:
> 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!.

Zgadza się.

>> 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ę :).

Tak. Ale teraz mówimy o implementacji.
Nie zaimplementujesz takiego pełnego drzewa
z 20! ~ 2^ 62 liścmi w pełni.

>
>> 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).

Dla 20?

> 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 :)).

Teoretycznie to ja rysuję drzewo i nie muszę tego
implementować;)
Sprzętowe sortowanie za pomocą pełnego drzewa decyzyjnego
dla 20 liczb? Jaja sobie robisz? ;) Oszczedza się kompa,
ale trzeba tone krzemu.

BTW, nie robi się tego za pomocą tworu zwanego siecią sortującą?

Nie chodzi o optymalizację? przecież zaczęło się do stwierdzenia
'potrzebuję posortować dużo 20, to biore optymalny algorytm
dla 20 elementó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 :).

Ładny. Ale widzisz różnicę między nim, a pełnym drzewem.
To się mieści w RAMie lub krzemie;)

pzdr
bartekltg