🚀 go-pugleaf

Jerzy Tarasiuk wrote:
> 
> O gorszych wynikach decyduje nie najgorszy przypadek, ktorego
> prawdopodobienstwo jest 1/n!, ale wystapienie znaczacej ilosci
> nieoptymalnych podzialow, co jakos calkiem czesto mi wychodzilo.
> 

Tu sie zgadzam... ale jezeli za kazdym razem wezmiemy mediane jako 
element wzgledem ktorwgo bedziemy dzielic, to ciag podzialow bedzie 
optymalny.

[...]
> 
> A nie, nie tak prosto: nie wystarczy jednokrotne znalezienie
> mediany (tak sie nazywa w ksiazce Wirtha element n/2), trzeba
> potem dzielic dalej, wynik jest O(n^2)... :-(

Troche chory jestem, wiec moze zle licze, ale mi n^2 nie wychodzi...

Wezmy ciag danych wejsciowych dlugosci n. Jezeli za kazdym razem 
dokonujemy optymalnego podzialu, to bedziemy mieli log n krokow ( Wirth, 
strona 93 ). Wobec tego czas dzialania algorytmu bedzie log(n)*O(t),
gdzie t - ograniczenie gorne na czas kroku; To sprobujmy policzyc t.
Zalozmy, ze wejsciowy ciag mamy podzielony na x czesci. Wowczas dla 
kazdej czesci musimy znalezc mediane ( czas O(n/x) = O(n), bo x jest 
stale ) oraz dokonac przestawien ( znowu O(n) ). Czyli dla kazdej z x 
czesci O(n)+O(n)=O(n) operacji. Czesci jest x, x jest stale, czyli dla 
calego ciagu dlugosci n wykonujemy x*O(n) = O(n) operacji. Czyli czas 
dzialania calego algorytmu to log n*(O(n))=O(n*log(n))

Tak mi wyszlo...
Lukasz Sznuk
lsz...@zodiac1.mimuw.edu.pl