Квадратичное время

Типичная задача: заданы n точек на плоскости, определяемых координатами (x,у); требуется найти пару точек, расположенных ближе всего друг к другу. Естествен- ный алгоритм «грубой силы» для такой задачи перебирает все пары точек, вы- числяет расстояния между каждой парой, а затем выбирает пару, для которой это расстояние окажется наименьшим.

Какое время выполнения обеспечит такой алгоритм? Количество пар точек

I j

а поскольку эта величина ограничивается —w^

границу O(n2). Проще говоря, количество пар ограничивается O(n2) потому, что количество способов выбора первого элемента пары (не больше n) умножается на количество способов выбора второго элемента пары (тоже не больше;?). Расстоя- ние между точками (x., у) и (x, у) вычисляется по формуле

11 J J

за постоянное время, так что общее время выполнения ограничивается O(n2).

В этом примере представлена очень распространенная ситуация, в которой встречается время выполнения O(n2): перебор всех пар входных элементов с по- стоянными затратами времени на каждую пару.

Квадратичное время так же естественно возникает в парах вложенных циклов: алгоритм состоит из цикла с O(n) итерациями, и каждая итерация цикла запускает внутренний цикл с временем O(n).

Произведение двух множителей n дает искомое время выполнения.

Эквивалентная запись алгоритм поиска ближайшей пары точек методом «гру- бой силы» с использованием двух вложенных циклов выглядит так:

Для каждой входной точки (xу.)

Для каждой из оставшихся входных точек (х., у.)

Вычислить расстояние

Если d меньше текущего минимума, заменить минимум значением d

Конец цикла Конец цикла

Обратите внимание: «внутренний» цикл по (х. , у.) состоит из O(n) итераций, каждая из которых выполняется за постоянное время, и «внешний» цикл по (х, у) состоит из O(n) итераций, каждая из которых один раз запускает вну- тренний цикл.

Важно заметить, что алгоритм, рассматриваемый нами для задачи ближайшей пары точек, в действительности относится к методам «грубой силы»: естественное пространство поиска этой задачи имеет размер O(n2), и мы всего лишь перебираем его. На первый взгляд может показаться, что в квадратичном времени есть некая неизбежность — ведь нам все равно придется перебрать все расстояния, не так ли? — но в действительности это всего лишь иллюзия. В главе 5 будет описан очень остроумный алгоритм для поиска ближайшей пары точек на плоскости за время всего лишь O(n log n), а в главе 13 мы покажем, как применение рандомизации со- кращает время выполнения до O(n).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика 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. Летнее время
  17. Прошлое время.