Что такое Quicker: использование Quicksort, затем двоичный поиск или просто линейный поиск?

Question

Если бы у меня был массив целых чисел с 1000 элементами, какой бы самый быстрый способ найти индекс конкретного элемента? Было бы лучше сначала выполнить QuickSort, а затем использовать BinarySearch или просто использовать простой старый LinearSearch?

Кроме того, будет ли самый быстрый способ отличаться, если бы у меня было 100 000 элементов или даже всего 100 элементов?

Спасибо!

Answer 1

Линейный поиск будет лучше. Худший случай O(N) для линейного поиска меньше, чем quicksort (средний O(nlog n), но в худшем случае O(N^2)) и тогда вам нужно будет добавить binarysearch (O(log N)). Сортировка и использование бинарного поиска будет лучше, если вам нужно много раз искать (если вы можете амортизировать стоимость сортировки, тогда бинарный поиск более эффективен, чем линейный поиск).

Answer 2

Накладные расходы быстрого сортирования - это O (n log (n)) в лучшем случае и O (n^2) в худшем случае, а двоичный поиск - O (log (n)), поэтому вместе в худшем случае они берут O (п^2).
Не нужно упоминать, что линейный поиск занимает O (n)
Так что это зависит от вашего количества операций и размера ввода. Вы можете умножить среднее время поиска в обоих наихудших случаях (k W (n), где k - это время поиска, а n - размер массива, а W (n) - наихудший случай каждого подхода), а затем решить, что делать.

Answer 3

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

Answer 4

Использование линейного поиска происходит быстрее, потому что оно будет принимать O(n) по сравнению с O(nlogn) время, затраченное на быстрое сортирование в одиночку. Однако, чтобы улучшить свое время в случае большого количества элементов, попробуйте создать несколько кусков массива и параллельно запустить алгоритм поиска. Посмотрите на PPL (библиотека Stl), чтобы узнать больше об этом.

Answer 5

Линейный поиск будет сравнивать каждый элемент с другим, чтобы найти соответствующий индекс.

Быстрая сортировка начнется с сравнения каждого элемента с точкой поворота, чтобы выполнить первый шаг разбиения. Затем происходит больше операций.

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