Wyszukiwanie binarne

Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
khaotic
Witam na forum
Witam na forum
Posty: 9
Rejestracja: 30 gru 2018, 13:24
Podziękowania: 4 razy

Wyszukiwanie binarne

Post autor: khaotic » 26 mar 2019, 10:03

Proszę o pomoc...


Załóżmy, że x-stronicowa książka telefoniczna zawiera uporządkowaną leksykograficznie listę nazwisk abonentów oraz, że otworzenie książki na stronie o dowolnie ustalonym numerze i stwierdzenie, czy to jest właściwa strona czy nie, zajmuje 1sek.

(a) Ile, co najwyżej, czasu potrzeba do wyszukania strony z dowolnym nazwiskiem, jeśli x=1024, a do poszukiwań zastosowano metodę binarnych poszukiwań?

(b) Ile co najwyżej osób figuruje w tej książce telefonicznej, jeśli wyszukanie metodą binarnych poszukiwań strony z dowolnym nazwiskiem zajmuje co najwyżej 6 sek., a na jednej stronie znajduje się dokładnie 25 nazwisk?

(c) Ile czasu zajęłoby wyszukiwanie nazwiska z ostatniej strony, jeśli x= 100, a do wyszukiwania zastosowaliśmy algorytm „skoki co 10” ?

Awatar użytkownika
KamilWit
Moderator
Moderator
Posty: 1484
Rejestracja: 07 lip 2011, 18:12
Podziękowania: 370 razy
Otrzymane podziękowania: 266 razy
Płeć:

Re: Wyszukiwanie binarne

Post autor: KamilWit » 04 sie 2020, 23:42

Warto zawsze zapoznać się ze złożonością algorytmu.
Złożoność wyszukiwania binarnego to \(O(log_2 n)\)

W przykładzie a) za n trzeba podstawić 1024.
Wynik to: \(O(log_2 1024) = 10 \)

b)
\(O(log_2 x) = 6
\)

\(x = 64
\)


Książka ma w takim razie 64 strony (lub mniej jakby się przyczepić zapisu zadania, ale na pewno nie więcej).

Wynik:
\(64*25=1600
\)


c) Zostawiam Tobie do spróbowania - poszukaj złożoności algorytmu.