2016-05-07 2 views
2

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

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

Спасибо!

+3

При каком значении n O (n) превосходит O (n log n)? Это поможет вам определить, что использовать –

+2

Для сортировки списка потребуется дополнительное усилие для восстановления индекса элемента, поскольку это, очевидно, разрушает простую связь между элементом массива и индексом элемента. –

+1

Связанные: http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o –

ответ

3

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

+0

Отлично! Вы могли бы объяснить мне нотацию O (N)? – 26hmkk

+3

Читайте статью в Википедии по [Большой записи нот] (https://en.wikipedia.org/wiki/Big_O_notation). –

1

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

1

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

1

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

1

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

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

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