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".
Moc obliczeniowa algorytmu wyszukiwania max metodą pucharowa
- kadiii
- Użytkownik
- Posty: 642
- Rejestracja: 20 gru 2005, o 21:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 130 razy
Moc obliczeniowa algorytmu wyszukiwania max metodą pucharowa
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
- Użytkownik
- Posty: 3454
- Rejestracja: 20 paź 2007, o 23:10
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 89 razy
- Pomógł: 353 razy
Moc obliczeniowa algorytmu wyszukiwania max metodą pucharowa
A bez logarytmów, albo tak kroczek po kroczku żebym zrozumiał i mógł wyjaśnić czemu tak, a nie inaczej da się??kadiii pisze: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}\)
- kadiii
- Użytkownik
- Posty: 642
- Rejestracja: 20 gru 2005, o 21:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 130 razy
Moc obliczeniowa algorytmu wyszukiwania max metodą pucharowa
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