Быстрая сортировка с последующим бинарным поиском быстрее, чем линейный поиск?

Question

Лучше ли сортировать, чем двоичный поиск или просто линейный поиск?

Спасибо

Answer 1

Это зависит от того, как часто вы хотите искать после сортировки - если только один раз, то линейный поиск, вероятно, будет быстрее.Конечно, еще лучшая ставка обычно (но не всегда) - поддерживать вещи в отсортированном порядке, используя что-то вроде set или карту.

Answer 2

Нет, потому что быстрая сортировка медленнее, чем линейная, и вы добавляете еще немного.

O(n*log(n)) + O(log(n)) = O(n*log(n)) > O(n)

Редактировать: Не совсем правильно, как указано, так как наихудший случай быстрой сортировки еще медленнее с O (n ^ 2). n * log (n) - лучший случай и средний случай, который обеспечивает нижнюю границу уже медленнее, чем линейная. Правильный символ может быть, однако, Θ вместо O.

Answer 3

Забвение двоичного поиска на минуту:

Быстрая сортировка наилучшего случая: O(n log n)

Быстрая сортировка худшего случая: O(n^2)

Линейный поиск худшего случая:n

Таким образом, независимо от того, что вы делаете после быстрой сортировки, вы уже нашли бы элемент, если бы выполнили линейный поиск.Однако это относится только к первому поиску.Скажем, у вас было более одного поиска.Если вы сохраните отсортированный список (Быстрый), то для всех последующих поисков будет наихудший случай O (log n), поэтому для нескольких поисков (особенно для больших наборов данных) сортировка и поиск будут целесообразными.Как всегда в программировании и разработке программного обеспечения в целом, никогда не бывает «одного размера для всех», поэтому необходимо подумать о том, какие шаблоны и реализации наиболее подходят для вашей конкретной области.

Answer 4

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

Answer 5

Это зависит от входа. Линейный поиск обычно быстрее для небольшого числа элементов.