Квадратичное время
Типичная задача: заданы 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).
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу