Метод декомпозиции, Master Theorem и Задача о паре ближайших точек

Метод «Разделяй и властвуй» (Divide and Conquer)

Парадигма состоит из 3 фундаментальных шагов:

Divide (Разделение): Разбиение задачи на несколько меньших подзадач того же типа;

Conquer (Властвование): Рекурсивное решение подзадач. Если размер подзадачи достаточно мал — прямое решение;

Combine (Объединение): Комбинирование решений подзадач в общее решение исходной задачи.

Основная теорема о рекуррентных соотношениях (Master Theorem)

Пусть рекуррентное соотношение имеет вид:

T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)

где

a \ge 1

— число подзадач,

b > 1

— фактор уменьшения размера задачи,

f(n)

— стоимость разделения и объединения.

Определим критическую функцию $n^{\log_b a}$ :

Случай 1: Доминирует рекурсия ( $f(n)$ полиномиально меньше $n^{\log_b a}$ )

Если

f(n) = O(n^{\log_b a - \varepsilon})

для некоторого

\varepsilon > 0

, то:

T(n) = \Theta(n^{\log_b a})

Случай 2: Баланс стоимости ( $f(n)$ и $n^{\log_b a}$ одного порядка)

Если

f(n) = \Theta(n^{\log_b a} \cdot \log^k n)

для

k \ge 0

, то:

T(n) = \Theta(n^{\log_b a} \cdot \log^{k+1} n)

Пример (MergeSort): $T(n) = 2T(n/2) + O(n) \implies a=2, b=2, n^{\log_2 2} = n^1 \implies T(n) = \Theta(n \log n)$ .

Случай 3: Доминирует работа на текущем уровне ( $f(n)$ полиномиально больше $n^{\log_b a}$ )

Если

f(n) = \Omega(n^{\log_b a + \varepsilon})

и выполняется условие регулярности

a f(n/b) \le c f(n)

при

c < 1

, то:

T(n) = \Theta(f(n))

Задача о паре ближайших точек на плоскости за $O(N \log N)$

Дано множество $P$ из $N$ точек на плоскости. Найти две точки с минимальным евклидовым расстоянием $d(p_i, p_j)$ .

cpp

struct Point { double x, y; };

double closestPairRec(vector<Point>& Px, vector<Point>& Py) {
    int n = Px.size();
    if (n <= 3) return bruteForce(Px);

    int mid = n / 2;
    Point midPoint = Px[mid];

    vector<Point> PxL(Px.begin(), Px.begin() + mid);
    vector<Point> PxR(Px.begin() + mid, Px.end());

    double dl = closestPairRec(PxL, Py);
    double dr = closestPairRec(PxR, Py);
    double d = min(dl, dr);

    // Полоса шириной 2*d вокруг разделяющей прямой x = midPoint.x
    vector<Point> strip;
    for (const auto& p : Py) {
        if (abs(p.x - midPoint.x) < d) strip.push_back(p);
    }

    // В полосе достаточно проверить не более 7-8 точек для каждой вершины!
    for (size_t i = 0; i < strip.size(); ++i) {
        for (size_t j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < d; ++j) {
            d = min(d, dist(strip[i], strip[j]));
        }
    }
    return d;
}

Метод декомпозиции, Master Theorem и Задача о паре ближайших точек

Метод «Разделяй и властвуй» (Divide and Conquer)

Основная теорема о рекуррентных соотношениях (Master Theorem)

Случай 1: Доминирует рекурсия (f(n)f(n)f(n) полиномиально меньше nlog⁡ban^{\log_b a}nlogb​a)

Случай 2: Баланс стоимости (f(n)f(n)f(n) и nlog⁡ban^{\log_b a}nlogb​a одного порядка)

Случай 3: Доминирует работа на текущем уровне (f(n)f(n)f(n) полиномиально больше nlog⁡ban^{\log_b a}nlogb​a)

Задача о паре ближайших точек на плоскости за O(Nlog⁡N)O(N \log N)O(NlogN)

Что дальше?

Случай 1: Доминирует рекурсия ( $f(n)$ полиномиально меньше $n^{\log_b a}$ )

Случай 2: Баланс стоимости ( $f(n)$ и $n^{\log_b a}$ одного порядка)

Случай 3: Доминирует работа на текущем уровне ( $f(n)$ полиномиально больше $n^{\log_b a}$ )

Задача о паре ближайших точек на плоскости за $O(N \log N)$