Сублинейное время
Наконец, в некоторых ситуациях встречается время выполнения, асимптотически меньшее линейного. Так как для простого чтения входных данных потребуется линейное время, такие ситуации обычно встречаются в модели вычислений с косвенными «проверками» входных данных вместо их полного чтения, а целью является минимизация количества необходимых проверок.
Пожалуй, самым известным примером такого рода является алгоритм бинарно- го поиска. Имеется отсортированный массив A из n чисел; требуется определить, принадлежит ли массиву заданное число p. Конечно, задачу можно решить чтени- ем всего массива, но нам хотелось бы действовать намного более эффективно — проверять отдельные элементы, используя факт сортировки массива.
Алгоритм проверяет средний элемент A и получает его значение (допустим, q), после чего q сравнивается с p. Если q = p, поиск завершается. Если q > p, то значение p может находиться только в нижней половине A; с этого момента верхняя половина A игнорируется, а процедура поиска рекурсивно применяется к нижней половине. Если же q < p, то применяются аналогичные рассуждения, а поиск рекурсивно продолжается в верхней половине A.
Суть в том, что на каждом шаге существует некая область A, в которой может находиться p; при каждой проверке размер этой области уменьшается вдвое. Каким же будет размер «активной» области A после k проверок? Начальный размер равен n, поэтому после k проверок он будет равен максимум .
Учитывая это обстоятельство, сколько шагов понадобится для сокращения активной области до постоянного размера? Значение k должно быть достаточно большим, чтобы , а для этого мы можем выбрать k = log2n. Таким образом, при k = log2 n размер активной области сокращается до константы; в этой
точке рекурсия прекращается, и поиск в оставшейся части массива может быть
проведен за постоянное время.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу