@tchdmevg

Что быстрее, простой поиск или сортировка + поиск?

Добрый день. Что работает быстрее, простой поиск или быстрая сортировка + бинарный поиск? Чем это обосновывается?
  • Вопрос задан
  • 103 просмотра
Решения вопроса 1
GavriKos
@GavriKos
Сложность простого поиска -n
Сложность бинарного поиска - Log(n)
А вот скорость быстрой сортировки неконстантна, и в худшем случае составляет n^2.

Так что однозначного ответа нет. Все зависит от входных данных.
Однако, если поиск делается часто, а данные не меняются (т.е. можно один раз отсортировать) - то определенно быстрее бинарный поиск.

Обосновывается это все математикой и ничем другим.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
gbg
@gbg
Баянист. Тамада. Услуги.
Линейный поиск - N
qsort - NlogN
Бинарный поиск logN

Для одноразового поиска - линейный поиск выигрывает
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через TM ID
Похожие вопросы