1. Jaka jest minimalna liczba porownan potrzebna do znalezienia dowolnego elementu w \(\displaystyle{ 64}\) elementowym zbiorze uporzadkowanym?
Odpowiedz to \(\displaystyle{ 6}\), ale jak do tego dojsc?
[Algorytmy] Sortowanie - minimalna liczba porownan
- Althorion
- Użytkownik
- Posty: 4541
- Rejestracja: 5 kwie 2009, o 18:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 9 razy
- Pomógł: 662 razy
[Algorytmy] Sortowanie - minimalna liczba porownan
\(\displaystyle{ \log_2 64 = 6}\). Zaczynasz od środka. Jeśli liczba jest mniejsza, to wybierasz tę połowę tablicy, która zawiera większe liczby, jeśli nie, to na odwrót. Powtarzasz do znalezienia szukanej liczby.
- snd0cff
- Użytkownik
- Posty: 199
- Rejestracja: 6 gru 2009, o 18:41
- Płeć: Mężczyzna
- Podziękował: 38 razy
- Pomógł: 10 razy
[Algorytmy] Sortowanie - minimalna liczba porownan
Jeszcze mam jedno pytanie:
Jak bedzie uporzadkowany nastepujacy zbior liczb \(\displaystyle{ \{5,11,4,9,3\}}\) po pierwszym etapie dzialania sortowania "szybkiego"
Z tego co wiem(a przynajmniej tak zinterpretowalem tekst) to bierzemy \(\displaystyle{ 4}\) (srodkowy wyraz) i na lewo liczby mniejsze \(\displaystyle{ (3)}\), a na prawo wieksze \(\displaystyle{ (5,11,9)}\) w takiej kolejnosci jak sa podane w zbiorze i wychodzi:
\(\displaystyle{ 3,4,5,11,9}\)
Co robie nie tak?
Jak bedzie uporzadkowany nastepujacy zbior liczb \(\displaystyle{ \{5,11,4,9,3\}}\) po pierwszym etapie dzialania sortowania "szybkiego"
Z tego co wiem(a przynajmniej tak zinterpretowalem tekst) to bierzemy \(\displaystyle{ 4}\) (srodkowy wyraz) i na lewo liczby mniejsze \(\displaystyle{ (3)}\), a na prawo wieksze \(\displaystyle{ (5,11,9)}\) w takiej kolejnosci jak sa podane w zbiorze i wychodzi:
\(\displaystyle{ 3,4,5,11,9}\)
Co robie nie tak?
Ostatnio zmieniony 23 sty 2013, o 21:08 przez Afish, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
- Althorion
- Użytkownik
- Posty: 4541
- Rejestracja: 5 kwie 2009, o 18:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 9 razy
- Pomógł: 662 razy
[Algorytmy] Sortowanie - minimalna liczba porownan
Nic, wszystko w porządku. Z tym że sam algorytm nic nie mówi o tym, który element brać jako rozgraniczający, zależy to od implementacji. Często bierze się pierwszy, środkowy (jak Ty to robisz), ostatni, losuje się albo specjalnie szuka najpierw mediany.
-
- Użytkownik
- Posty: 363
- Rejestracja: 24 sie 2012, o 09:27
- Płeć: Mężczyzna
- Lokalizacja: Cieszyn
- Pomógł: 80 razy
[Algorytmy] Sortowanie - minimalna liczba porownan
Mam wątpliwość co do odpowiedzi na pierwsze pytanie. Bo to raczej pokazanie, że 6 wystarcza, a raczej trzeba pokazać, że nie istnieje algorytm, który by dla każdych danych potrzebował mniej niż 6.
Czyli, że nie istniej o mniejszej złożoności pesymistycznej.
Czyli, że nie istniej o mniejszej złożoności pesymistycznej.
- Althorion
- Użytkownik
- Posty: 4541
- Rejestracja: 5 kwie 2009, o 18:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 9 razy
- Pomógł: 662 razy
[Algorytmy] Sortowanie - minimalna liczba porownan
To raczej szkic dowodu w obu przypadkach. Żeby go wzmocnić, musimy się powołać na fakt, że jeśli nie dzielimy danych na połowy, to pesymistycznie za każdym razem może nam szukana wartość wypadać w tej większej części; tak więc aby zminimalizować czas działania algorytmu należy dążyć do tego, by te części były równe.