Сублинейное время

Наконец, в некоторых ситуациях встречается время выполнения, асимптотически меньшее линейного. Так как для простого чтения входных данных потребуется ли- нейное время, такие ситуации обычно встречаются в модели вычислений с косвен- ными «проверками» входных данных вместо их полного чтения, а целью является минимизация количества необходимых проверок.

Пожалуй, самым известным примером такого рода является алгоритм бинарно- го поиска.

Имеется отсортированный массив A из n чисел; требуется определить, принадлежит ли массиву заданное числор. Конечно, задачу можно решить чтени- ем всего массива, но нам хотелось бы действовать намного более эффективно — проверять отдельные элементы, используя факт сортировки массива. Алгоритм проверяет средний элемент A и получает его значение (допустим, q), после чего q сравнивается с р. Если q = р, поиск завершается. Если q > р, то значение р может находиться только в нижней половине A; с этого момента верхняя половина A игнорируется, а процедура поиска рекурсивно применяется к нижней половине. Если же q < р, то применяются аналогичные рассуждения, а поиск рекурсивно продолжается в верхней половине A.

Суть в том, что на каждом шаге существует некая область A, в которой может находиться р; при каждой проверке размер этой области уменьшается вдвое. Каким же будет размер «активной» области А после к проверок? Начальный размер равен

и, поэтому после к проверок он будет равен максимум

Учитывая это обстоятельство, сколько шагов понадобится для сокращения активной области до постоянного размера? Значение к должно быть достаточно

а для этого мы можем выбрать к = log2n. Таким

образом, при к = log2 n размер активной области сокращается до константы; в этой точке рекурсия прекращается, и поиск в оставшейся части массива может быть проведен за постоянное время.

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

2.5.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Сублинейное время:

  1. Время сейчас такое – время мудрости пришло!
  2. 14. 4. Рабочее время и время отдыха
  3. Зарубка на носу Дай время себе, дай время ребенку
  4. Время
  5. Время
  6. Время
  7. Время
  8. Всемирное время.
  9. Местное время.
  10. 1.2.2. Время отдыха
  11. 1.2.1 Рабочее время
  12. ВРЕМЯ
  13. ВРЕМЯ РЕАКЦИИ
  14. «Время»
  15. Настоящее время.
  16. Летнее время