ТМВ-2020-Лекция-04.02.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - Вычислительная сложность алгоритмов. Амортизационный анализ.

Разрешающие деревья

Разрешающее дерево - бинарное дерево, в котором каждая вершина содержит некоторое действие, в случае сортировки - сравнение. Из каждой вершины выходит два ребра, одно из них достигается, если i-й элемент больше j-го; другое - если i-й элемент меньше j-го. Вычисление на конечном наборе входных значений (массив чисел) происходит следующем образом: в начале вычисления мы находимся в корне дерева. Находясь в какой-либо вершине, мы смотрим на значения i-го и j-го элементов. Если i-й элемент больше j-го, то переходим в следующую вершину по 1-му ребру(левому), если i-й элемент меньше j-го, то переходим в следующую вершину по 2-му ребру(правому). На листьях(выходе) мы получаем итоговую перестановку \(\pi\).

Вычислительная сложность алгоритма сортировки

Бинарное дерево сравнения
Бинарное дерево сравнения

Минимальное количество сравнений - длина пути из корня в лист. В массиве всего n элементов, соответственно листьев будет: $$m \geq \log_2 m \geq \log_2 n! \approx /$$по Формуле Стирлинга $$n! \sim \sqrt{2\pi n}(\frac{n}{у})^n/ \approx \log_2{\sqrt{2\pi n}(\frac{n}{l})^n} = const + n\log_2 n \approx n\log_2 n$$

Бинарный счётчик

Бинарный счётчик

Бинарный счетчик – массив, состоящий из \(n\) бит, в котором записано двоичное число, и определена одна операция - инкремент: \(Inc()\) (сложность операции \(O(n)\)).

Пример счётчика:
1 0 1 ... 1 0 0
1 2 3 ... n-2 n-1 n
Пример операции
Исходный массив
0 1 1 1 1 1
Результирующий массив(применение Inc())
1 0 0 0 0 0

Если цепь из \(m\) инкрементов: сложность \(O(m*n)\), в хорошем случае \(O(m)\).

Значения не всех битов меняются m раз

Посмотрим на изменения ячеек при проведении операции \(Inc()\) \(m\) раз.

Оценка сложности

Оценка сложности:$$m + \frac{m}{2} + \frac{m}{2^2} + \frac{m}{2^n} + \ldots \le \sum_{i=0}^\infty \frac{m}{2^i} = m\sum_{i=0}^\infty \frac{1}{2^i} = 2m$$
Пояснение:

$$q + q^2 + \ldots + q^n = Q_n$$

$$q(1 + q + \ldots + q^{n - 1} + q^n - q^n) = q(1 + Q_n - q^n) = Q_n$$

$$q + qQ_n - q^{n + 1} = Q_n$$

$$Q_n = \frac{q-q^{n + 1}}{1 - q} \to \frac{q}{1 - q} ($$при $$n \to \infty)$$

Амортизационный анализ

Наряду с получением верхних и нижних оценок и оценок в среднем, часто используются так называемые амортизационные оценки. Амортизационный анализ — подход к оценке вычислительной сложности алгоритма. Амортизационный анализ применяется при оценке времени выполнения корректной последовательности, состоящей из однотипных или разнотипных операций с некоторой структурой данных. Учетная сложность - сложность в среднем на длительной цепочке операций.

Метод потенциалов

$$S_1 \to_{t_1}^{op} S_2 \to_{t_2}^{op} \ldots \to_{t_{m+1}}^{op} S_{m+1}$$

\(S\) – структура данных

\(t_i\) - время выполнения операции(истинная стоимость операции)

\(op\) - операции

Справедлива формула:

$$t_{i+1} = c_{i+1} + \Phi_i - \Phi_{i+1}$$

\(c_{i+1}\) - учётная(приведённая) стоимость операции

\(\Phi_{i+1}\) - потенциал (функция состояния, принимает на вход текущее состояние структуры данных и возвращает некоторое неотрицательное число)

$$\sum_{i=1}^mt_i = \sum_{i=1}^m(c_i + \Phi_i - \Phi_{i+1}) = \sum_{i=1}^mc_i + \Phi_1 - \Phi_m$$ (если правая часть данного выражения является ограниченной, то алгоритм является линейным)

Если \(c_i = const\), то \(\sum_{i=1}^mt_i = mc + \Phi_i - \Phi_m = O(mc + \Phi_i - \Phi_m ) \)

Пример: задача про бинарный счётчик

Как нужно выбрать функцию потенциала с тем, чтобы скорректированная с помощью этой функции потенциала стоимость оказалась равномерно ограничена по всем операциям?

Потенциалом состояния назовем число единиц в этом состоянии \( \Phi\) - количество единиц

Разность потенциалов – количество ячеек, в которые вносим изменения.

Бинарный счётчик

\(\Phi_i - \Phi_{i+1} = -(k - 1)\)

\(t_{i+1} = k+1 = c_{i+1} + \Phi_i - \Phi_{i+1} = t_{i+1} + k - 1 \Rightarrow c_i = 2\)

\(O(mc + \Phi_1 - \Phi_m) = O(2m + 0 - 0\) (пояснение: минимальная оценка)\() = O(m)\)

Динамический массив

Пусть динамический массив строится так:

1) Изначально он пуст

2) Элементы добавляются в него по одному. При исчерпании места в массиве выделяется новый участок памяти, в котором зарезервировано дополнительно \(l\) элементов

3) Все уже присутствовавшие в массиве элементы копируются в новый участок памяти

4) Добавляется очередной элемент.

Сколько суммарно копирований элементов необходимо осуществить, если всего добавляется \(n=kl\) элементов?

На первом шаге мы копируем \(l\) элементов, затем \(2l\), затем \(3l\), и так далее, вплоть до \(n-l\) элементов. Сумма этих количеств:

$$\sum_{i=1}^{k-1}il=l\sum_{i=1}^{k-1}i= \frac{lk(k-1)}{2} \equiv \frac{lkk}{2} = \frac{n^2}{2l}=O(\frac{n^2}{l})$$

"Нормальная" стратегия:

"Нормальная" стратегия
"Нормальная" стратегия

\(\Phi = s - n\)

\(t_{i+1} = c_{i+1} - n_i + s_i + n_{i+1} = c_{i+1} - 1 = 1 \Rightarrow c_{i+1} = 2\)

\(t_{i+1} = s_i + 1 = c_{i+1} - n_i + s_i + n_{i+1} - s_{n+1} = c_{i+1} + 2s_i -s_i - 1 = c_{i+1} + s_i - 1 = s_i + 1\)

\(sum_{i=1}^mt_i = O(m -2 +1) = O(m)\)

\(n + \frac{n}{2} + \frac{n}{4} + \cdots + \frac{n}{2^m} \le 2n\)