Сравнение последовательного поиска с бинарным поиском

Question

Предположим, у меня есть несортированный массив действительных чисел, длины N, Я хочу найти наибольшее неположительное число yа затем первый номер x меньше чем y в массиве, и первый номер z больше чем y,

Я хотел бы теоретически сравнить последовательный поиск с бинарным поиском не асимптотически (т.е. не только с большим Os), чтобы найти эти значения. Разумно ли заявить:

• Последовательный поиск требует
  • 0 сравнения для сортировки,
  • 3*N сравнения для поиска (три последовательных поиска).
• Бинарный поиск требует
  • 2*N*ln(N) ≈ 1.39*N*log_2(N) сравнения для сортировки ( быстрая сортировка, средняя),
  • вплоть до log_2(N) сравнения для поиска (только один поиск, так как массив отсортирован, и поэтому мы можем посмотреть на соседние значения в отсортированном массиве, чтобы найти x а также z как только мы нашли y).

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

1.39*N*log_2(N) + log_2(N) < 3*N 
<=> 
0 < N < 3.44779

т.е. только для очень маленьких массивов?

Answer 1

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

Answer 2

Нет, это неверный вывод по нескольким причинам.

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