W dniu niedziela, 14 października 2012 01:33:48 UTC+2 użytkownik bartekltg napisał:
> 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.
Jak duze musi byc pelne drzewo decyzyjne? Poczatkowo mamy N! mozliwych
permutacji. Pierwsza instrukcja IF powoduje ze mam pewnosc co do
kolejnosci dwoch elementow. Jesli N==20, to po pierwszym IF nie
wiemy nic o 18tu elementach. Daje to 18! ciagow. Pozostale dwa elementy
moga byc wplecione w te 18 na 19*19 sposobow. 20! / ( 18! * 19^2 ) = 1.0526.
Po pierwszym IFie ilosc permutacji spadla o okolo 5%. O ile spadnie z
kazdym nastepnym ifem?
Pozdrawiam




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