Бинарный поиск против последовательного поиска/точка безубыточности

Question

Я действительно борюсь с этим вопросом домашней работы. Мой профессор делает ужасную работу, объясняя что-либо. Помогите?

Существует некоторая компромисс между сортировкой списка, а затем использованием двоичного поиска и просто использованием последовательного поиска в несортированном списке. Выбор зависит от того, сколько раз будет просматриваться список. Предположим, что для последовательного поиска требуется n сравнений в худшем случае, для сортировки требуются n * log n сравнения, а для двоичного поиска требуется log n сравнения в худшем случае (где log - это база данных 2, как мы уже обсуждали). Учитывая несортированный список из 1024 элементов (т. Е. Log 1024 = 10), сколько поисковых запросов потребуется для сортировки, чтобы быть полезной? Предположим, что средний случай для последовательного поиска требует n/2 сравнений. Теперь, какова точка безубыточности для s?

Подсказка: Напишите выражение для количества сравнений, необходимых для поиска по каждому методу; затем установите их равными и решите для s.

Answer 1

Вы сравниваете время, которое необходимо для выполнения первоначального рода (стоимость: n*log(n)) и последующего двоичного поиска (стоимость: log(n)). Итак, если вы хотите найти s раз, вы будете платить начальный n*log(n), чтобы отсортировать список и log(n) для каждого (двоичного) поиска. То есть:

c1 = (n*log(n)) + (s*log(n)) = (n+s)*log(n) 

Вместо этого, если вы выполняете линейный поиск, нет «первоначальной стоимости», но каждый поиск будет стоить n, поэтому для s поиска:

c2 = s*n 

Очевидно, для s и n достаточно маленький, c2 меньше, потому что такой начальной стоимости нет, но это растет быстрее чем c1. В определенный момент будут пересекаться c1 и c2. То есть c1 = c2.

                 n * log(n) 
s * n = (n + s) * log(n) --> s * (n - log(n)) = n * log(n) --> s = ------------ 
                    n - log(n) 

Ну, теперь вам нужно обсудить приведенное выше уравнение. Этот участок должен сказать вам все:

Answer 2

В качестве подсказки: работа делается для сортировки п, а затем сделать K двоичного поиска задается

н лог п + к логу н

и работа, необходимая, чтобы сделать K последовательных запросов является

пк

Если n = 1000, для какого значения k вторая величина будет меньше первой?

Надеюсь, это поможет!