Autor: Andrzej Lewandowski (lewando_at_ibm.net)
Data: Thu 05 Mar 1998 - 14:09:12 MET
lewando_at_ibm.net (Andrzej Lewandowski) wrote:
>Jacek Pietraszek <pmpietra_at_cyf-kr.edu.pl> wrote:
>
>>A jakie odpowiedzi byly sensowne? :-)
>Nalezy tablice przeksztalcic do "sterty" (heap). Po takiej operacji
>ktora kosztuje O(logN) (log dwojkowy), pierwszy element tablicy jest
>najwiekszy. Nalezy go usunac wykonujac operacje "bubble-down". Ta
>operacja tez kosztuje O(logN). W wyniku tejze, pierwszy element
>tablicy bedzie drugim co do wielkosci. "Bubble-down" nalezy wiec
>powtorzyc 10 razy. Znalezienie p-tej co do wielkosci liczby bedzie
>mialo zlozonosc O(p logN). Jezeli p = N, to posortujemy cala tablice.
>Dla N=20,000,000 10logN jest w przyblizeniu 250.
>Problem jest z zycia. "Informatycy" zaprojektowali pewien system i
>przetestowali go na przykladzie o wymiarowosci 5 na 5. Potem dali do
>klienta ktory przetestowal go na przykladzie 5000 na 5000. Mowili ze
>"problem sie zle skaluje".
OK. napisalem nieprawde. Zrobilem skrot. Bije sie w piersi.
Rzeczywisty problem byl troche bardziej skomplikowany: do tablicy
dodaje sie nowe elementy periodycznie, za kazdym razem trzeba znalezc
element maksymalny (lub p-ty). W przypadku JEDNORAZOWEGO wyszukiwania
p-tego elementu nie oplaca sie stosowac sterty. Dlaczego? Co w
powyzszym tekscie napisalem nieprawidlowo?
A.L.
To archiwum zostało wygenerowane przez hypermail 2.1.7 : Tue 18 May 2004 - 17:04:26 MET DST