Autor: Andrzej Lewandowski (lewando_at_ibm.net)
Data: Thu 05 Mar 1998 - 04:12:31 MET
Jacek Pietraszek <pmpietra_at_cyf-kr.edu.pl> wrote:
>Andrzej Lewandowski <lewando_at_ibm.net> wrote:
>: P.S. Niedawno przeprowadzalem test w duzej firmie wsrod Wybitnych
>: Programistow (Senior Software ENGINEER, itd). Problem sprowadzal sie
>: mniej wiecej do tego": "W pamieci jest 20 milionow liczb w
>: przypadkowej kolejnosci. Znalezc 10 do do wielkosci". NIKT nie
>: udzielil sensownej odpowiedzi. Nadmieniam, ze odpowiedz "posortowac i
>: znalezc dziesiata" NIE jest sensowna. Zreszta malo kto wiedzial ze
>: jest wiecej niz jedna metoda sortowania...
>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".
A.L.
To archiwum zostało wygenerowane przez hypermail 2.1.7 : Tue 18 May 2004 - 17:04:25 MET DST