В базе данных хранится 1 048 576 = 2^20 записей. Оцените количество сравнений, которое придётся сделать при использовании линейного и двоичного поиска по одному из полей. Во сколько раз быстрее работает двоичный поиск?
В базе данных хранится 1 048 576 = 2^20 записей. Оцените количество сравнений, которое придётся сделать при использовании линейного и двоичного поиска по одному из полей. Во сколько раз быстрее работает двоичный поиск?
Гость
Ответ(ы) на вопрос:
ГостьЛинейный поиск в худшем случае сравнит все элементы, 2^20 сравнений.
Бинарный поиск в худшем случае сделает примерно log(2^20) = 20 сравнений.
Бинарный поиск работает в 2^20 / 20 ~ 50 000 быстрее
Не нашли ответ?
Похожие вопросы