Page 275 - Bkhargava_-_Grokaem_algoritmy
P. 275

Ответы к упражнениям


















        Глава 1


        1.1   Имеется отсортированный список из 128 имен, и вы ищете в нем зна­
             чение методом бинарного поиска. Какое максимальное количество
             проверок для этого может потребоваться?

             Ответ: 7

        1.2   Предположим, размер списка увеличился вдвое. Как изменится мак­
             симальное количество проверок?
             Ответ: 8

        1.3   Известна фамилия, нужно найти номер в телефонной книге.

             Ответ: O(log п)

        1.4   Известен номер, нужно найти фамилию в телефонной книге. (Под­
             сказка: вам придется провести поиск по всей книге!)

             Ответ: О(п).

        1.5   Нужно прочитать номера всех людей в телефонной книге.
             Ответ: О(п).


        1.6   Нужно прочитать телефоны всех людей, фамилии которых начинают­
             ся с буквы «А». (Вопрос с подвохом! В нем задействованы концепции,
             которые более подробно рассматриваются в главе 4.  Прочитайте от­
             вет -  скорее всего, он вас удивит!)


                                                         www.trk.kg
   270   271   272   273   274   275   276   277   278   279   280