Быстрее n · log n нельзя - и когда всё-таки можно

Если ты знаешь, как сортировка сводится к оболочке, в какой модели верна граница n · log n, что такое алгоритм Чана и сколько вершин у оболочки случайных точек, листай до «Теперь сам».

Как думаешь, можно ли быстрее

Цепочка Эндрю тратит на стеки линейное время, и вся цена - сортировка. Напрашивается вопрос: может, сортировка оболочке и не нужна? Заворачивание подарка ведь обходится без неё. Может быть, есть хитрый алгоритм, который строит оболочку за линейное время в худшем случае?

Ответь себе до чтения: какой довод мог бы доказать, что такого алгоритма нет? Перебирать все алгоритмы невозможно. Ответ урока: достаточно показать, что быстрая оболочка дала бы быструю сортировку. А о сортировке такой довод уже есть - в разделе о сортировках курс доказал, что сортировка сравнениями требует порядка n · log n сравнений.

На что это похоже

Если по рецепту из готового торта можно за минуту восстановить список продуктов в порядке закупки, то испечь торт не может быть быстрее, чем составить этот список. Не нужно знать всех кондитеров мира: достаточно одной инструкции «торт → список». Задача, к которой свели другую, не легче той, что к ней сведена.

Здесь «торт» - оболочка, «список» - отсортированные числа, а инструкция - парабола.

Механизм: сведение через параболу и что оно доказывает

Сведение. Дано n чисел. Превращаем каждое x в точку (x, x²) - это n шагов. Все точки лежат на параболе y = x², а парабола выпуклая: отрезок между любыми двумя её точками лежит выше дуги между ними. Поэтому каждая точка - вершина оболочки, а обход оболочки против часовой стрелки от самой левой точки идёт по нижней границе слева направо - то есть по возрастанию x. Прочитать x из вершин - ещё n шагов.

сортировка(числа)  <=  n  +  оболочка(n точек)  +  n

Если бы оболочка стоила o(n · log n), сортировка стоила бы столько же. А это невозможно - значит, оболочка стоит не меньше порядка n · log n.

В какой модели. Граница сортировки верна для алгоритмов, которые узнают о данных только сравнениями. Для оболочки нужна более широкая модель - алгебраическое дерево решений: на каждом шаге алгоритм вычисляет многочлен от координат и выбирает ветку по его знаку. Поворот и есть многочлен второй степени, а число разных ответов (порядков) слишком велико, чтобы различить их меньше чем за n · log n таких шагов. Для неё та же граница доказана (Бен-Ор, 1983). Вне этой модели граница не действует: если координаты - целые от 0 до U, их сортируют подсчётом за n + U, и оболочка строится за n + U. Граница говорит о модели вычислений, а не о законе природы.

Чувствительность к выходу. Сведение строит вход, где все точки - вершины. Если вершин h мало, граница другая: n · log h. Её достигает алгоритм Чана (1996). Идея: разбить точки на группы по m, построить оболочку каждой группы Эндрю за n · log m, а потом заворачивать подарок, но выбирать следующую вершину не перебором всех точек, а двоичным поиском касательной в каждой маленькой оболочке - log m на группу: у выпуклого многоугольника, если идти по кругу, знак поворота «текущая вершина → ребро» меняется ровно дважды - в двух точках касания, - и нужную смену находят делением пополам. Если m ≥ h, всё стоит n · log m. Самого h алгоритм не знает и угадывает его: m = 4, 16, 256, … - каждый раз квадрат прежнего, пока заворачивание не замкнётся за m шагов.

Правило

Сортировка сводится к оболочке через параболу (x, x²), поэтому в модели «решения знаками многочленов от координат» оболочка требует Ω(n · log n). Чувствительная к выходу граница - Θ(n · log h) при h ≥ 2, её достигает алгоритм Чана. Вне модели - например, для маленьких целых координат - граница не действует.

Разбор: оболочка сортирует

Возьмём заворачивание подарка - в нём нет ни одной сортировки - и дадим ему точки на параболе.

def povorot(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def dal(a, b):
    return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2

def dzharvis(tochki):
    # оболочка без всякой сортировки - заворачивание подарка
    start = min(tochki)
    obolochka = []
    tek = start
    while True:
        obolochka.append(tek)
        kand = tochki[0]
        if kand == tek:
            kand = tochki[1]
        for p in tochki:
            if p == tek:
                continue
            z = povorot(tek, kand, p)
            if z < 0 or (z == 0 and dal(tek, p) > dal(tek, kand)):
                kand = p
        tek = kand
        if tek == start:
            break
    return obolochka

chisla = [7, -3, 12, 0, 5, -8, 3, 9]
tochki = []
for x in chisla:
    tochki.append([x, x * x])
o = dzharvis(tochki)
otvet = []
for p in o:
    otvet.append(p[0])
print(otvet)

[-8, -3, 0, 3, 5, 7, 9, 12]

Числа отсортированы, хотя, кроме выбора стартовой точки через min, программа не сравнивала числа - только считала повороты. Сортировку сделала геометрия: на выпуклой кривой порядок обхода и есть порядок по x. Заворачивание стоит здесь n², и сортировкой его никто пользоваться не станет. Важен сам факт: любой алгоритм оболочки в этой обёртке становится сортировкой - и не может быть быстрее её.

Разбор: сколько вершин у случайных точек

Сведение использует худший вход - все точки на оболочке. На реальных данных так почти не бывает. Сосчитаем вершины оболочки случайных точек в квадрате и в круге.

import random

def povorot(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def endryu(tochki):
    t = sorted(tochki)
    niz = []
    for p in t:
        while len(niz) >= 2 and povorot(niz[-2], niz[-1], p) <= 0:
            niz.pop()
        niz.append(p)
    verh = []
    for p in t[::-1]:
        while len(verh) >= 2 and povorot(verh[-2], verh[-1], p) <= 0:
            verh.pop()
        verh.append(p)
    return niz[:-1] + verh[:-1]

random.seed(7)
R = 10000  # сетка 20001 × 20001 - почти непрерывно

for n in [100, 400, 1600]:
    kvadrat = []
    krug = []
    while len(krug) < n:
        x = random.randint(-R, R)
        y = random.randint(-R, R)
        kvadrat.append([x, y])
        if x * x + y * y <= R * R:
            krug.append([x, y])
    kvadrat = kvadrat[:n]
    print(n, len(endryu(kvadrat)), len(endryu(krug)))

100 12 15
400 15 20
1600 21 43

В квадрате вершин 12, 15, 21 - при росте n в 16 раз их стало меньше чем вдвое больше. Теория говорит: в среднем около (8/3) · ln n, логарифм. В круге - 15, 20, 43, рост быстрее: в среднем порядка n^(1/3). Разница понятна из формы: у квадрата углы, и точки возле сторон, но вдали от углов, почти никогда не оказываются крайними; у круга граница везде одинаково выпуклая.

Отсюда практический вывод: на случайных данных h мало, и алгоритмы, чувствительные к выходу, выигрывают. На том же держится простая эвристика Экла и Туссена (1978): найти четыре крайние точки - например, с наименьшей и наибольшей суммой x + y и разностью x − y, это точки у углов квадрата, - выбросить всё, что лежит внутри их четырёхугольника, и только остаток отдать полноценному алгоритму. На точках в квадрате выбрасывается почти всё.

Что ломается без этого

«Нашёл линейный алгоритм оболочки». Если проверка «на всех тестах линейно» прошла, значит, в тестах h маленькое или координаты маленькие. На точках параболы любой честный алгоритм сравнений и поворотов покажет n · log n или хуже.

Перенос границы туда, где её нет. Пиксели изображения - целые от 0 до 4000. Оболочка по ним строится за линию после сортировки подсчётом, и «оптимальный» n · log n здесь не оптимален.

Заворачивание на круге. Точки, расставленные по окружности, - не экзотика: датчики вокруг объекта, вершины правильного многоугольника, точки контура фигуры. Там h = n, и n · h превращается в n².

Зачем это в работе

Сведения - главный способ понять, что задачу не ускорить, и перестать пробовать. Если кто-то обещает построить триангуляцию ДелонеРазбирается в разделе 23, глава «Триангуляция Делоне и её свойства»: Триангуляции точек: сколько в них треугольников и почему важны углы или диаграмму ВороногоРазбирается в разделе 23, глава «Локализация точки, kd-дерево, диаграмма Вороного»: Диаграмма Вороного: у каждого объекта своя область ближайших точек «за линию», вспомни: обе дают выпуклую оболочку бесплатно, значит, обе не дешевле сортировки.

В трёх измерениях оболочка тоже стоит n · log n, а её размер линеен: по формуле Эйлера у выпуклого многогранника с n вершинами не больше 2n − 4 граней. Именно это строит scipy.spatial.ConvexHull через библиотеку Qhull - алгоритм «быстрой оболочки», который рекурсивно откладывает самую дальнюю от грани точку.

Теперь сам

1. По сведению отсортируй 4, −1, 2: какие точки строишь и в каком порядке их выдаст оболочка?
2. У алгоритма Чана m = 16, а оболочка на самом деле имеет 40 вершин. Что произойдёт?
3. Почему сведение не доказывает, что заворачивание подарка медленнее n · log n на любом входе?