Autor: Michal Mosiewicz (mimo_at_interdata.com.pl)
Data: Thu 05 Mar 1998 - 15:11:13 MET
Andrzej Lewandowski wrote:
> W przypadku JEDNORAZOWEGO wyszukiwania
> p-tego elementu nie oplaca sie stosowac sterty. Dlaczego? Co w
> powyzszym tekscie napisalem nieprawidlowo?
Nie jestem senior software engineer ale chyba zamiana tablicy na stóg
nie jest wcale operacją O(logN). Stawiałbym raczej na O(NlogN).
W sumie ten problem wymaga wykonania conajmniej N porównań. Jeśli wiemy,
że elementy nie są w żaden sposób poukładane to raczej nie będzie ich
mniej, bo żadnej z liczb nie można przecież pominąć. Można więc
udowodnić, że problem ma złożoność nie mniejszą niż O(N).
W takim przypadku problem jest taki jak znalezienie maksimum z
nieuporządkowanej tablicy, tyle, że zamiast szukać jednego maksimum
musimy znaleźć 10 maksymalnych wartości. Zapamiętując 10 najwyższych
elementów w podręcznej posortowanej tablicy będziemy musieli w
pesymistycznym przypadku przeprowadzić 10N porównań oraz 10N przestawień
w tablicy podręcznej. Przeciętnie będzie nieco ponad 2N porównań. W ten
sposób wiadomo, że problem ma złożoność nie większą niż O(N).
Zdałem? :-)
Michał
-- WWW: http://www.lodz.pdi.net/~mimo tel: Int. Acc. Code + 48 42 148340 add: Michal Mosiewicz * Bugaj 66 m.54 * 95-200 Pabianice * POLAND
To archiwum zostało wygenerowane przez hypermail 2.1.7 : Tue 18 May 2004 - 17:04:27 MET DST