Стоит еще обратить
Стоит еще обратить внимание, что предлагаемый вариант функции, как и ранее рассмотренный E2-1, работает для подмассива. Что касается быстродействия, то в "большом" массиве дихотомия заметно опережает последовательный поиск. Поскольку на каждом шаге алгоритма интервал поиска уменьшается вдвое, то количество шагов не превосходит ?log2N?, соответственно, асимптотическая эффективность метода половинного деления оценивается как O(log2N).
Пример #2.
Сравните: при N=1000 последовательный поиск требует, в среднем, 500 шагов, а дихотомия - только 10.
Подведем промежуточные итоги. В отношении нескольких алгоритмов, обсуждавшихся в этой главе, можно сказать, что они применимы как для вектора, так и к массивам бОльших размерностей. Это относится к алгоритмам E1-1, E2-1, E2-2, - разве что понадобятся некоторые "косметические" изменения. Но вот алгоритм E3-1 явно использует отличительные особенности линейной структуры данных, каковой является вектор.
Рассмотрим еще несколько
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
