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

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

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

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

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

Для  каждой  входной  точки  (xi,  yi)

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

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

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

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

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

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

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