Задать вопрос
20 марта, 21:10

В базе данных хранится 1 048 576 = 2^20 записей. Оцените количество сравнений, которое придётся сделать при использовании линейного и двоичного поиска по одному из полей. Во сколько раз быстрее работает двоичный поиск?

+4
Ответы (1)
  1. 20 марта, 22:34
    0
    Линейный поиск в худшем случае сравнит все элементы, 2^20 сравнений.

    Бинарный поиск в худшем случае сделает примерно log (2^20) = 20 сравнений.

    Бинарный поиск работает в 2^20 / 20 ~ 50 000 быстрее
Знаете ответ?
Сомневаетесь в ответе?
Найдите правильный ответ на вопрос ✅ «В базе данных хранится 1 048 576 = 2^20 записей. Оцените количество сравнений, которое придётся сделать при использовании линейного и ...» по предмету 📘 Информатика, а если вы сомневаетесь в правильности ответов или ответ отсутствует, то попробуйте воспользоваться умным поиском на сайте и найти ответы на похожие вопросы.
Смотреть другие ответы
Похожие вопросы по информатике
Выберите операции, которые можно выполнять в базах данных: А. Поиск информации по запросу. Б. Добавление столбцов. В. Фильтрация данных по указанному критерию. Г. Удаление записей. Д. Дублирование записей. Е. Редактирование записей.
Ответы (2)
Что меняется при сортировке базы данных? 1-Число полей 2-Порядок записей 3-Число записей 4-Порядок полей
Ответы (1)
Что значит подсчитать кол-во сравнений? (программа уже написана (без подсчета), мне просто нужно объяснить, что это) Уровень A. Заполнить массив случайными числами и отсортировать его. Ввести число X.
Ответы (1)
Какого типа информации в поисковых системах не существует: а) поиск по любому из слов в) поиск по всем словам с) поиск по синонимам д) поиск точно по фразе
Ответы (1)
В базе данных хранятся записи о датах. Каждая запись состоит из трех полей: год (число от 1 до 2100), месяц (число от 1 до 12), день месяца (число от 1 до 31). Каждое из полей кодируется отдельно с использованием минимально возможного количества бит.
Ответы (1)