Wyszukiwanie binarne
: 26 mar 2019, 09: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” ?
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” ?