Moc obliczeniowa algorytmu wyszukiwania max metodą pucharowa

[smigol]

Jaka jest moc obliczeniowa algorytmu wyszukiwania wartości maksymalnej metodą pucharową, dla zbioru n-elementowego.
Oczywiscie dla samej wartości maxymalnej jest prosto.
Ale chodzi mi o to jak będzie wyglądał ten wzór dla znalezienia "wicemistrza".

[kadiii]

Rozumiem, że przez moc rozumiesz ilość wykonanych operacji. Tak więc aby znaleźć wicemistrza należy wykonać \(\displaystyle{ n+log _{2}n-2}\) operacje porównań. Liczba n-1 to oczywiście znalezienie mistrza i teraz z drugiej części poddzrewa usuwamy mistrza i wykonujemy tyle operacji ile jest poziomów w drzewie pomijająć dolne, które już znamy czyli \(\displaystyle{ log _{2}n-1}\). Razem wspomniane już\(\displaystyle{ n+log _{2}n-2}\)

[smigol]

Rozumiem, że przez moc rozumiesz ilość wykonanych operacji. Tak więc aby znaleźć wicemistrza należy wykonać \(\displaystyle{ n+log _{2}n-2}\) operacje porównań. Liczba n-1 to oczywiście znalezienie mistrza i teraz z drugiej części poddzrewa usuwamy mistrza i wykonujemy tyle operacji ile jest poziomów w drzewie pomijająć dolne, które już znamy czyli \(\displaystyle{ log _{2}n-1}\). Razem wspomniane już\(\displaystyle{ n+log _{2}n-2}\)

A bez logarytmów, albo tak kroczek po kroczku żebym zrozumiał i mógł wyjaśnić czemu tak, a nie inaczej da się??

[kadiii]

Najłatwiej to rozrysuj sobie takie drzewko(drabinkę) pucharową -chyba wiadomo jak wygląda. Znajdowanie zwycięzcy to wiadomo jak(napisałeś, że wiesz. Teraz wykonujemy podstawienie, zamiast mistrza zastępujemy zawodnikiem słabszym od wszystkich innych(żeby przegrał pierwszy mecz) oraz anulujemy wszystkie mecze mistrza. Teraz korzystając z wyników uzyskanych podczas szukania mistrza musimy rozegrać dodatkowo tyle meczów ile poziomów ma drzewo(drabinka rozgrywek) - dla pełnego drzewa jest ich \(\displaystyle{ log _{2} n}\). Żeby ci ułatwić i bez tego logarytmu to można tak pomyśleć, pełne drzewo(drabinka) ma liczbę zawodników będącą potęgą dwójki, mamy więc \(\displaystyle{ n=2^{k}}\). Liczba zawodników w każdej rundzie maleje o połowę, liczba k jest więc ilością takich rund(ilością poziomów w drzewie). teraz jedynie zerknij na definicje logarytmu a zobaczysz, że \(\displaystyle{ log _{2}n=k}\). Trzeba rozegrać więc dodatkowo \(\displaystyle{ log _{2}n}\) meczów - tyle, ze wynik meczu z udziałem najsłabszego zawodnika(spójrz powyżej) jest znany, wiec pomijamy ten poziom - ostatecznie mamy \(\displaystyle{ log _{2}n -1}\) a doliczając mecze, które rozgrywamy, żeby wyznaczyć zwycięzce mamy \(\displaystyle{ n+log _{2}n-2}\) meczów do rozegrania. mam nadzieję, że w miarę jasne. Pozdrawiam