Сортировка и двоичный поиск или просто линейный поиск?

Question

Проблема

Временная сложность выбора рода есть n*(n-1)/2. Учитывая список из 1000 пунктов, сколько наихудших поисков по поиску, используя линейный поиск, необходимо, прежде чем быстрее сортировать и использовать двоичный поиск?

Попытка раствора

Временная сложность двоичного поиска является floor(log(n)/log(2)+1). Следовательно, временная сложность одного выбора сортировки, за которым следуют двоичные запросы x, равна n*(n-1)/2+x*floor(log(n)/log(2)+1). Сложность времени линейного поиска равна n, поэтому сложность времени x линейных поисковых запросов составляет x*n.

Таким образом, мы устанавливаем равенство x*n=n*(n-1)/2+x*floor(log(n)/log(2)+1), что для n=1000 дающий x=5550/11 и, следовательно, floor(x)=floor(5550/11)=504. Это верно?

Answer 1

Вы пытаетесь добиться гораздо большей точности, чем вы можете получить от простого числа операций. Чтобы получить точный номер, вам нужно будет учитывать такие вещи, как кеш процессора (линейный поиск, вероятно, немного его использует).

Чтобы получить идею общего назначения, мы можем рассмотреть сложность большого О. (Ожидаемая) сложность сортировки - O (N log N). Сложность двоичного поиска - O (log N), поэтому сложность M бинарных поисков - O (M log N). Общая сложность сортировки, а затем двоичного поиска приблизительно равна O ((N + M) log N).

Для линейного поиска сложность одного поиска - O (N), поэтому сложность поиска M - это O (NM).

Таким образом, для N = 1000, то точка безубыточности должна быть apprxoimately:

(1000 + M) * .log (1000) = 1000 М.

Это примерно: (1000 + M) * 10 = 1000 М.

Если мы отменим константы и разрыва, мы получаем: 1000 + M = 100M, то: (1000 + M)/100 = M

Дистрибуция, мы получаем: 1000/100 + M/100 = M

Вычитания, а затем разделив константы, получает до: 10 = .99M

Водораздельных, мы получаем по существу M = 10.

Таким образом, не обращая внимание различия в постоянных факторах, наша точка безубыточности РЕКОМЕНДУЕМЫХ около 10 поисков.

На реальном процессоре, я бы Угадай Большинство из этих постоянных факторов (прогнозирование ветвей, использование кеша и т. Д.) Имеют тенденцию к линейному поиску в двоичном поиске в некоторой степени (т. Е. Линейный поиск работает с кеш и его ветви очень предсказуемы), поэтому мы ожидаем, что линейный поиск останется быстрее, чем бинарный поиск, до нескольких поисков, чем это, вероятно, по меньшей мере до 20 поисков и, возможно, до 50 или 100 ,

Возможно, есть еще один фактор, который следует учитывать. Для 1000 предметов сортировка Shell-Metzner с приблизительно O (N ^1.2) сложность может очень хорошо в конечном итоге несколько быстрее, чем Quicksort. По моему опыту, это часто составляет около 1500-2000 предметов. То есть, если что-то еще более сложно оценить с какой-либо реальной точностью, поэтому я просто собираюсь предположить, что есть хороший шанс, что это немного уменьшит точку безубыточности.