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

Question

[Дмитрий]

Добрый день. Что работает быстрее, простой поиск или быстрая сортировка + бинарный поиск? Чем это обосновывается?

Answer 1

[GavriKos]

Сложность простого поиска -n
Сложность бинарного поиска - Log(n)
А вот скорость быстрой сортировки неконстантна, и в худшем случае составляет n^2.

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

Обосновывается это все математикой и ничем другим.

Answer 2

[Армянское Радио]

Линейный поиск - N
qsort - NlogN
Бинарный поиск logN

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

Comments

[GavriKos]

У qsort разве константная сложность? Она ж напрямую зависит от изначальных данных и может быть (судя по вики) n^2.

Но на ответ это в целом не влияет )

[Владимир Олохтонов]

У quicksort nlogn в среднем, n^2 в худшем случае.

Его всегда можно заменить на mergesort и получить стабильный nlogn.