Page 279 - Bkhargava_-_Grokaem_algoritmy

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

«Adit В» в конец списка. Теперь предположим, что зарегистрировать
нужно пользователя «Zakhir Н». Вы обращаетесь к элементу 26, ко­
торый содержит связанный список всех имен, начинающихся с «Z~,
И проверяете, присутствует ЛИ «Zakhir Н~ В ЭТОМ списке.
Теперь сравните эту гибридную структуру данных с массивами и свя­
занными списками. Будет она быстрее или медленнее каждой исход­
ной структуры при поиске и вставке? Приводить время выполнения
«О-большое» не нужно, просто выберите одно из двух: быстрее или
медленнее.
Ответ: Поиск - медленнее, чем для массивов, и быстрее, чем для
связанных списков. Вставка - быстрее, чем для массивов, и с такой же
скоростью для связанных списков. Итак, гибридная структура уступа­
ет массиву по скорости поиска, но по крайней мере не хуже связанных
списков для всего остального. Далее в книге будет рассмотрена другая
гибридная структура данных, называемая хеш-таблицей. Она даст не­
которое представление о том, как строить сложные структуры данных
из более простых.

Что же в действительности использует сервис Facebook? Вероятно,
десяток разных баз данных, за которыми стоят разные структуры
данных: хеш-таблицы, в-деревья и т. д. Массивы и связанные списки
становятся структурными элементами для построения более сложных
структур данных.

Глава З

3.1 Предположим, имеется стек вызовов следующего вида:

Что можно сказать о текущем состоянии программы на основании
этого стека вызовов?

www.trk.kg