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

Question

Это прямая цитата из учебника Приглашение к информатике Дж. Майкла Скнейдера и Джудит Л. Герстинг.

В конце Раздела 3.4.2 мы говорили о компромиссе между использованием последовательного поиска по несортированному списку в отличие от сортировки списка и последующим использованием двоичного поиска. Если размер списка равен n = 100 000, сколько нужно выполнить поиск в худшем случае, прежде чем второй вариант станет лучше с точки зрения количества сравнений?

Я не совсем понимаю, о чем вопрос.

Последовательный поиск имеет порядок (n), а двоичный - порядка (lgn), который в любом случае всегда будет меньше ngn. И в этом случае n уже дано, так что я должен найти.

Это одно из моих домашних заданий, но я не знаю, что делать. Может ли кто-нибудь объяснить мне вопрос простым языком?

Answer 1

и двоичный файл имеет порядок (lgn), который в любом случае всегда будет меньше n
Это где ты не прав. При назначении вас также просят учесть стоимость сортировки массива.

Очевидно, что если вам нужен только один поиск, первый подход лучше, чем сортировка массива и выполнение бинарного поиска: n < n*logn + logn. И вас спросят, сколько поисков вам нужно, чтобы второй подход стал более эффективным.

Конец подсказки.

Answer 2

Вопрос в том, как решить, какой подход выбрать - просто использовать линейный поиск или отсортировать, а затем использовать бинарный поиск.

Если вы ищете только пару раз, линейный поиск лучше - это O (n), а сортировка уже O (n * logn). Если вы часто выполняете поиск в одной и той же коллекции, сортировка лучше - поиск несколько раз может стать O (n * n), но сортировка и последующий поиск с помощью бинарного поиска снова O (n * logn) + NumberOfSearches * O (logn) меньше или больше, чем при использовании линейного поиска, в зависимости от того, как связаны NumberOfSearches и n.

Задача состоит в том, чтобы определить точное значение NumberOfSearches (не точное число, а функция n), что сделает один из вариантов предпочтительным:

 NumberOfSearches * O(n) <> O(n*logn) + NumberOfSearches * O(logn)

не забывайте, что каждый O () может иметь различное постоянное значение.

Answer 3

Порядок методов здесь не важен. Это говорит вам о том, насколько хорошо масштабируются алгоритмы, когда проблема становится все больше и больше. Вы не можете делать точные вычисления, если знаете только O(n) ==, что сложность возрастает в зависимости от размера задачи. Он не даст вам никаких цифр.

Это может означать, что алгоритм со сложностью O(n) быстрее, чем алгоритм O(logn), для некоторого n. Поскольку O (log (n)) масштабируется лучше, когда он становится больше, мы точно знаем, что существует n (размер проблемы), где алгоритм со сложностью O (logn) работает быстрее. Мы просто не знаем когда (для чего n).

На простом английском языке:

Если вы хотите знать, «сколько поисков», вам нужны точные уравнения для решения, вам нужны точные числа. Сколько сравнений нужно, чтобы искать последовательно? (Помните, что задано n, поэтому вы можете указать число.) Сколько сравнений (в худшем случае!) Требуется для поиска с помощью двоичного поиска? Прежде чем вы сможете выполнить бинарный поиск, вы должны отсортировать. Давайте добавим количество сравнений, необходимых для сортировки, к стоимости бинарного поиска. Теперь сравните два числа, какое из них меньше?

Бинарный поиск быстрый, но сортировка медленная. Последовательный поиск медленнее, чем бинарный поиск, но быстрее, чем сортировка. Однако сортировку необходимо выполнить только один раз, независимо от того, сколько раз вы выполняете поиск. Итак, когда одна тяжелая сортировка перевешивает необходимость каждый раз выполнять медленный (последовательный) поиск?

Удачи!

Answer 4

Спасибо, ребята.Я думаю, теперь я понял.Не могли бы вы взглянуть на мой ответ и посмотреть, нахожусь ли я на правильном пути.

Для поиска в худшем случае Количество сравнений для последовательного поиска составляет n = 100 000.Количество сравнений для двоичного поиска равно lg (n) = 17. Количество сравнений для сортировки равно (n-1) / 2 * n = (99999) (50000).(Я следую своему учебнику и использовал алгоритм сортировки выбора, описанный в моем классе)

Итак, пусть p будет числом поисков в худшем случае, затем 100 000p> (99999) (50000) + 17p
ИЛИ p> 50008

В заключение, мне нужно 50 008 поисков в худшем случае, чтобы сделать сортировку и использовать бинарный поиск лучше, чем последовательный поиск по списку с n = 100 000.

Answer 5

Вопрос в том, чтобы оценить число NUM_SEARCHES, необходимое для компенсации стоимости сортировки.Итак, у нас будет:

 time( NUM_SEARCHES * O(n) ) > time( NUM_SEARCHES * O(log(n)) + O(n* log(n)) )