Бинарный поиск против простого поиска

Question

Согласно книгам по алгоритмам производительность двоичного поиска равна O (log n), а для простого поиска - O (n).

Но почему бы нам не принять во внимание время, затрачиваемое на сортировку, которое является обязательным условием для бинарного поиска?

Answer 1

Короче говоря : потому что обычно построение этого списка выполняется только один раз, тогда как поиск (и обновление) выполняется несколько раз.

Для построения отсортированного списка действительно требуется O (n log n) . Смысл использования бинарного поиска заключается в том, что после сортировки коллекции мы можем выполнить несколько запросов в этом списке, каждый с O (log n) .

Кроме того, если вы, например, используете двоичное дерево поиска, вы можете выполнить вставку и удаление элементов в O (log n) , поэтому обновление коллекции может быть дешево (если вы используете для этого эффективную структуру данных).

Например, в базе данных часто используются индексы для быстрого поиска. Обычно количество операций чтения велико по сравнению с количеством обновлений. Обновление одного элемента требует O (log n) , поэтому создание индекса для существующих данных действительно дорого, но это не очень распространено по сравнению с поиском и обновлением B-дерева структура данных [wiki] .

Answer 2

Предполагается, что данные будут сохранены уже отсортированными.Поскольку данные не нужно пересортировать каждый раз при выполнении поиска, они не учитываются в Big O.