Двоичный и линейный поиск для несортированных N элементов

Question

Я пытаюсь понять формулу, когда мы должны использовать быструю сортировку.Например, у нас есть массив с N = 1_000_000 элементами.Если мы будем искать только один раз , мы должны использовать простой линейный поиск , но если мы сделаем это 10 раз, мы должны использовать массив сортировки O (n log n).Как я могу определить порог, когда и для какого размера входного массива я должен использовать сортировку, а после этого использовать бинарный поиск?

Answer 1

При условии n элементов и m поисков с приблизительными значениями

• стоимость сортировки составит C0.n.log n,

• стоимость m бинарных поисков C1.m.log n,

• стоимость m линейных поисков C2.m.n,

с C2 ~ C1 < C0.

Теперь вы сравниваете

C0.n.log n + C1.m.log n vs. C2.m.n

или

C0.n.log n / (C2.n - C1.log n)  vs. m

Для достаточно больших n точка безубыточности составляет около C0.log n / C2.

Например, взятие C0 / C2 = 5, n = 1000000 дает m = 100.

Answer 2

Это фактически превратилось в интересный вопрос для меня, когда я посмотрел на ожидаемое время выполнения алгоритма, подобного быстрой сортировке, когда ожидаемое разделение на каждом уровне не 50/50.
Первый вопрос, на который я хотел ответить, был дляслучайные данные, что среднее разделение на каждом уровне.Конечно, оно должно быть больше 50% (для более крупного подразделения).Ну, учитывая массив размером N случайных значений, наименьшее значение имеет подразделение (1, N-1), второе наименьшее значение имеет подразделение (2, N-2) и т. Д. Я положил это вБыстрый скрипт:

split = 0
for x in range(10000):
  split += float(max(x, 10000 - x)) / 10000
split /= 10000
print split

И получил ровно 0,75 в качестве ответа.Я уверен, что смогу показать, что это всегда точный ответ, но я хотел перейти к более сложной части.

Теперь, давайте предположим, что даже 25/75 разделение следует за прогрессом nlogn для некоторого неизвестного логарифмабаза.Это означает, что num_comparisons(n) = n * log_b(n), и вопрос заключается в том, чтобы найти b с помощью статистических средств (поскольку я не ожидаю, что эта модель будет точной на каждом этапе).Мы можем сделать это с умным применением аппроксимации наименьших квадратов после того, как мы используем логарифмическую идентификацию, чтобы получить:

C(n) = n * log(n) / log(b)

, где теперь логарифм может иметь любую базу, если log(n) и log(b)использовать ту же базу.Это линейное уравнение, ожидающее некоторых данных!Поэтому я написал другой скрипт для генерации массива xs, заполнил его C(n) и ys, заполнил его n*log(n) и использовал numpy, чтобы сообщить мне наклон этой наименьших квадратов, который я ожидаюравным 1 / log(b).Я запустил скрипт и получил b внутри [2.16, 2.3] в зависимости от того, как высоко я установил n (я менял n от 100 до 100'000'000).Тот факт, что b, кажется, меняется в зависимости от n, показывает, что моя модель не точна, но я думаю, что это нормально для этого примера.

Чтобы ответить на ваш вопрос сейчас, с этими предположениями, мыможет решить для точки отсечения, когда: N * n/2 = n*log_2.3(n) + N * log_2.3(n).Я просто предполагаю, что бинарный поиск будет иметь ту же базу логарифма, что и метод сортировки для разбиения 25/75.Изолировав N, вы получите:

N = n*log_2.3(n) / (n/2 - log_2.3(n))

Если число ваших поисков N превышает количество в RHS (где n - размер рассматриваемого массива), тогда оно будет более эффективнымотсортировать один раз и использовать двоичный поиск по этому.

Answer 3

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

n*log[b](n) + x*log[2](n) <= x*n/2 x - количество поисков;n размер ввода;b Основание логарифма для сортировки, в зависимости от используемого вами разбиения.

Когда этот оператор оценивается как true, следует переключить методы с линейного поиска на сортировку и поиск.

Вообще говоря, линейный поиск по неупорядоченному массиву займет в среднем n / 2 шага, хотя это среднее значение будет играть большую роль только при приближении x к n.Если вы хотите использовать большие обозначения Omicron или Theta, то можете опустить /2 в приведенном выше.

Answer 4

Вы хотите решить неравенство, которое может быть описано как

t * n > C * n * log(n) + t * log(n)

, где t - число проверок, а C - некоторая постоянная для реализации сортировки (должна быть определена экспериментально).Когда вы оцениваете эту константу, вы можете решить неравенство численно (с неопределенностью, конечно)

Answer 5

Вы должны построить сложности обеих операций.

Линейный поиск: O (n)

Сортировка и двоичный поиск: O (nlogn + logn)

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