Autor: milosz danielewski (mdaniel_at_friko.onet.pl)
Data: Sat 07 Mar 1998 - 00:33:47 MET
On Thu, 05 Mar 1998 03:12:31 GMT, lewando_at_ibm.net (Andrzej
Lewandowski) wrote:
>Nalezy tablice przeksztalcic do "sterty" (heap). Po takiej operacji
>ktora kosztuje O(logN) (log dwojkowy),
Podstawa logarytmu sie chyba nie liczy, bo to mnozenie przez stala,
tzn. O(const*logN) ( oczywiscie przy zapisie zlozonosci !)
> 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.
A tak w ogole, to jaka operacje, biezemy do obliczania kosztu ? Bo
chyba musimy choc raz przeczytac i porownac wszystkie elementy z
tablicy...
milosz danielewski
To archiwum zostało wygenerowane przez hypermail 2.1.7 : Tue 18 May 2004 - 17:04:28 MET DST