Алгоритмы C++

Асимптотика

Математическое ожидание

Утверждается, что математическое ожидание оценивается сверху логарифмом от числа вершин в этой куче:

Тогда справедливо:

что и требовалось доказать.

Превышение ожидаемой оценки

Докажем, что вероятность превышения полученной выше оценки мала:

для любой положительной константы .

что и требовалось доказать.

Асимптотика алгоритма

Таким образом, алгоритм , а, значит, и все остальные выраженные через него операции, выполняется за в среднем.

Более того, для любой положительной константы найдётся такая положительная константа , что вероятность того, что операция потребует больше чем операций, меньше (это в некотором смысле описывает

худшее поведение алгоритма).

Задача RMQ (Range Minimum Query - минимум на отрезке)

Дан массив A[1..N]. Поступают запросы вида (L, R), на каждый запрос требуется найти минимум в массиве A, начиная с позиции L и заканчивая позицией R.

Приложения

Помимо непосредственного применения в самых разных задачах, можно отметить следующие: ● Задача LCA (наименьший общий предок)

Решение

Задача RMQ решается с помощью структур данных.

Из описанных на сайте структур данных можно выбрать:

●Sqrt-декомпозиция - отвечает на запрос за O (sqrt (N)), препроцессинг за O (N). Преимущество в том, что это очень простая структура данных. Недостаток - асимптотика.

●Дерево отрезков - отвечает на запрос за O (log N), препроцессинг за O (N).

Преимущество - хорошая асимптотика. Недостаток - бОльший объём кода по сравнению с другими структурами данных.

●Дерево Фенвика - отвечает на запрос за O (log N), препроцессинг за O (N log N)

Преимущество - очень быстро пишется и работает тоже очень быстро. Но значительный недостаток - дерево Фенвика может отвечать только на запросы с L = 1, что для многих приложений неприменимо.

Примечание. "Препроцессинг" - это предварительная обработка массива A, фактически это построение структуры данных для данного массива.

Теперь предположим, что массив A может изменяться в процессе работы (т.е. также будут поступать запросы об изменении значения в некотором отрезке [L;R]). Тогда полученную задачу можно решить с помощью

Sqrt-декомпозиции и Дерева отрезков.

Длиннейшая возрастающая подпоследовательность за O (N2)

Это одна из основных задач на динамическое программирование.

Нередко задачу именуют как LIS (longest increasing subsequence).

Дана последовательность M[1..N]. Строим таблицу A[1..N]. Каждый её элемент Ai - длина длиннейшей

возрастающей подпоследовательности, оканчивающейся точно в позиции i. Если мы построим эту таблицу, то ответ к задаче - наибольшее число из этой таблицы.

Само построение тоже элементарно: Ai = max (Aj+1), среди всех j < i, для которых Mj < Mi. Перый элемент A1 = 1, что очевидно.

Таким образом, алгоритм работает за O (N2).

Реализация

int main()

{

vector<int> m; // последовательность int n; // её длина

... // считываем последовательность

vector<int> a (n, 1); // таблица длин a[0] = 1;

vector<int> pred (n, -1); // таблица предков, если надо вывести и саму подпоследовательность

for (int i=1; i<n; i++)

for (int j=0; j<i; j++) if (m[j] < m[i])

if (a[j]+1 > a[i])

{

a[i] = a[j]+1;

pred[i] = j;

}

// выводим длину последовательности

cout << * max_element (a.begin(), a.end());

// ищем и выводим саму подпоследовательность vector<int> result;

for (int cur = int (max_element (a.begin(), a.end()) - a.begin()); cur != -1; cur = pred[cur])

result.push_back (m[cur]); cout << endl;

for (unsigned i=result.size(); i-- > 0; ) cout << result[i] << ' ';

}

Длиннейшая возрастающая подпоследовательность за O (N log N)

Здесь мы рассмотрим улучшенный алгоритм, который работает за более быструю асимптотику, чем описанный здесь. Мы также будем применять метод динамического программирования, правда, немного по-другому поставим задачу.

Пусть по условию дан массив чисел A длиной N. Вычислим массив D[0..N], каждый элемент которого D[i] есть число, на которое оканчивается возрастающая подпоследовательность длины i (если таких чисел несколько, то

берётся наименьшее). Очевидно, этот массив можно легко вычислить за O (N2):

// O (N2)

vector<int> d (n+1, INF); d[0] = -INF;

for (int i=0; i<n; i++)

for (int j=0; j<i; j++)

if (d[j] < a[i] && a[i] < d[j+1]) d[j+1] = a[i];

Однако теперь легко догадаться, как ускорить вычисление массива D - нужно использовать бинарный

поиск. Действительно, вместо того, чтобы перебирать всевозможные индексы j, мы воспользуемся очевидным свойством D[i] <= D[i+1] и применим бинарный поиск (в данном случае upper_bound):

// O (N log N) vector<int> d (n+1, INF); d[0] = -INF;

for (int i=0; i<n; i++)

{

unsigned j = upper_bound (d.begin(), d.end(), a[i]) - d.begin() - 1; if (d[j] < a[i] && a[i] < d[j+1])

d[j+1] = a[i];

}

Если теперь при обновлении массива D сохранять в дополнительных массивах предков, то становится легко найти саму подпоследовательность:

// O (N log N) vector<int> d (n+1, INF); d[0] = -INF;

vector<int> p (n); vector<int> no (n+1); no[0] = -1;

for (int i=0; i<n; i++)

{

unsigned j = upper_bound (d.begin(), d.end(), a[i]) - d.begin() - 1; if (d[j] < a[i] && a[i] < d[j+1])

{

d[j+1] = a[i]; p[i] = no[j]; no[j+1] = i;

}

}

vector<int> result;

for (int i=n; i>=1; i--) if (d[i] != INF)

{

for (int cur=no[i]; cur!=-1; cur=p[cur]) result.push_back (cur);

break;

}

reverse (result.begin(), result.end()); for (unsigned i=0; i<result.size(); i++)

cout << a[result[i]] << ", ";

K-ая порядковая статистика за O (N)

Пусть дан массив A длиной N и пусть дано число K. Задача заключается в том, чтобы найти в этом массиве K-ое по величине число, т.е. K-ую порядковую статистику.

Основная идея - использовать идеи алгоритма быстрой сортировки. Собственно, алгоритм несложный, сложнее доказать, что он работает в среднем за O (N), в отличие от быстрой сортировки.

Реализация в виде нерекурсивной функции:

template <class T>

T order_statistics (std::vector<T> a, unsigned n, unsigned k)

{

using std::swap;

for (unsigned l=1, r=n; ; )

{

if (r <= l+1)

{

//текущая часть состоит из 1 или 2 элементов -

//легко можем найти ответ

if (r == l+1 && a[r] < a[l]) swap (a[l], a[r]);

return a[k];

}

// упорядочиваем a[l], a[l+1], a[r] unsigned mid = (l + r) >> 1;

swap (a[mid], a[l+1]); if (a[l] > a[r])

swap (a[l], a[r]); if (a[l+1] > a[r])

Динамика по профилю. Задача "паркет"

Типичными задачами на динамику по профилю, являются:

●найти количество способов замощения поля некоторыми фигурами

●найти замощение с наименьшим количеством фигур

●найти замощение с минимальным количеством неиспользованных клеток

●найти замощение с минимальным количеством фигур такое, что в него нельзя добавить ещё одну фигуру

Задача "Паркет"

Имеется прямоугольная площадь размером NxM. Нужно найти количество способов замостить эту площадь фигурами 1x2 (пустых клеток не должно оставаться, фигуры не должны накладываться друг на друга).

Построим такую динамику: D[I][Mask], где I=1..N, Mask=0..2^M-1. I обозначает количество строк в текущем поле, а Mask - профиль последней строки в текущем поле. Если j-й бит в Mask равен нулю, то в этом месте профиль проходит

на "нормальном уровне", а если 1 - то здесь "выемка" глубиной 1. Ответом, очевидно, будет D[N][0].

Строить такую динамику будем, просто перебирая все I=1..N, все маски Mask=0..2^M-1, и для каждой маски будем делать переходы вперёд, т.е. добавлять к ней новую фигуру всеми возможными способами.

Реализация:

int n, m;

vector < vector<long long> > d;

void calc (int x = 0, int y = 0, int mask = 0, int next_mask = 0)

{

if (x == n) return;

if (y >= m)

d[x+1][next_mask] += d[x][mask];

else

{

int my_mask = 1 << y;