Асимптотические оценки сложности. Асимптотически точная оценка функции роста. Удаление элемента из дерева
Асимптотические обозначения
Если для функции T (n ) найдутся константы c 1 > 0 и c 2 > 0 и такое число n 0 > 0, что выполнится условие , то говорят что время выполнения алгоритма (программы) асимптотически точно соответствует функции n 2 . Этот факт обозначается как , где n – длина входа алгоритма.
Определение 1. Вообще, если и положительно определенные функции, то запись означает, что найдутся константы c 1 > 0 и c 2 > 0 и такое n 0 > 0, что для всех .
(Запись « » читается как «эф от эн есть тэта от же от эн»).
Если , то говорят, что является асимптотически точной оценкой (asymptotically tight bound) для . На самом деле это отношение симметрично, если: , то .
Рис. 2. Иллюстрация к определению
Заметим, что есть обозначение факта некоторого соотношения между двумя функциями, поэтому, если установлено , а следовательно и , то это вовсе не означает, что .
Проиллюстрируем свойство симметрии функции . Можно показать, что . Согласно определению надо указать положительные константы с 1 , с 2 и число n 0 так, чтобы неравенства
выполнялись для всех . Разделим все части неравенства на n 2 :
Видно, что для выполнения второго неравенства достаточно положить c 2 = 1/2. Первое будет выполнено, если (например) n 0 = 7 и c 1 =1/14.
Покажем, что В самом деле, пусть найдутся такие c 2 и n 0 , что для всех . Но тогда для всех , из чего следует что c 2 не может является константой, так как растет с увеличением n , что противоречит определению.
Упомянем важный частный случай использования -обозначений: , который обозначает ограниченную функцию, отделённую от нуля некоторый положительной константой при достаточно больших значениях аргумента.
Асимптотические обозначения часто употребляются внутри формул. Например, рекуррентное соотношение вида
означает, что время выполнения алгоритма для входа длины n определяется временем выполнения для входной последовательности из (n –1) элементов и некоторой функции, про которую нам важно знать лишь, что она не меньше c 1 n и не больше c 2 n для некоторых положительных с 1 и с 2 и для всех достаточно больших n , которая по определению обозначается через . Иными словами, время работы программы при изменение входной длины увеличивается пропорционально n , а в алгоритме этому члену в выражении соответствует фрагмент с асимптотической оценкой равной n .
Часто асимптотические обозначения употребляются не вполне формально, хотя их подразумеваемый смысл обычно ясен из контекста.
Типичный пример неформального использования асимптотических обозначений – цепочка равенств вида . Второе из этих равенств понимается при этом так: какова бы ни была функция в левой части, сумма есть .
Отыскивая асимптотически точную оценку для суммы, мы можем отбрасывать члены меньшего порядка, которые при больших n становятся малыми по сравнению с основным слагаемым. Заметим также, что коэффициент при старшем члене роли не играет (он может повлиять только на выбор констант с 1 и с 2). Например, рассмотрим квадратичную функцию , где a, b, c – некоторые константы и a > 0. Отбрасывая члены младших порядков и коэффициент при старшем члене, находим что Чтобы убедиться в этом формально, можно положить с 1 = a/ 4, c 2 = 7a/ 4и . Вообще, для любого полинома p(n) степени d с положительным старшим коэффициентом имеем .
1.3.2 - и - обозначения
Вообще, запись включает в себя две оценки: верхнюю и нижнюю. Их можно разделить:
Определение 2. Пусть имеются функции и , которые принимают неотрицательные значения для достаточно больших значений аргумента. Говорят, что , если найдётся такая константа c > 0 и такое число n 0 , что для всех (рис. 3а).
Определение 3. Говорят, что , если найдётся такая константа c > 0 и такое число n 0 , что для всех (рис. 3б). Эти записи читаются так: «эф от эн есть о большое от же от эн», «эф от эн есть омега большая от же от эн».
Теорема 1.Для любых двух функций и свойство выполнено тогда и только тогда, когда и .
Замечание: Для любых двух функций и свойство и равносильны.
(а) (б)
Рис. 3. Верхняя (а) и нижняя (б) асимптотические оценки функции
Асимптотические обозначения могут употребляются внутри формул. Например, мы можем написать выражение
имея в виду сумму h (1) + h (2) + … + h (n ), где h (×) – некоторая функция, для которой h (i ) = O (i ). Можно показать, что сама эта сумма как функция от n есть O(n 2).
1.3.3 и обозначения
Запись означает, что с ростом n отношение остаётся ограниченным. Если к тому же
то мы пишем (читается «эф от эн есть о малое от же от эн»). Формально говоря, , если для всякого положительного найдётся такое n 0 , что при всех . Тем самым запись предполагает, что и неотрицательны для достаточно больших n .
Пример: но
Аналогичным образом вводится обозначение: говорят, что есть («эф от эн есть омега малая от же от эн»), если для всякого положительного e найдется такое n 0 , что при всех , причем
Очевидно, равносильно
Пример: , но
Таким образом, может существовать три основных случая (существует и четвертый случай, когда предела не существует, однако он встречается довольно редко в реальной практике анализа алгоритмов):
Однако на практике строгими определениями пользуются редко. Существует более удобный метод выполнения этой оценки, основанный на мощном математическом аппарате, специально созданного для вычисления пределов отношения двух рассматриваемых функций, в частности правилом Лопиталя (L"Hopital):
и формулой Стирлинга (Stirling) для достаточно больших n :
Пример 1 . Сравните порядки роста функций f (n )=n (n – 1)/2 и g (n )=n 2 .
Решение: поскольку
предел равен положительной константе, обе функции имеют одинаковый порядок роста, что записывается как .
Пример 2 . Сравните порядки роста функций и .
Поскольку предел равен нулю, функция имеет меньший порядок роста, чем . То есть .
Пример 3. Сравните порядки роста функций и .
Решение: воспользовавшись формулой Стерлинга, получим:
Следовательно, хотя функция растет очень быстро, функция растет еще быстрее, что записывается как . Обратим внимание, что при использовании этой формы записи, в отличие от случая использования пределов, не можем сделать однозначный вывод о том, что порядок роста функции выше, чем функции , а не, скажем, равен ей, поэтому используется «большая» омега.
Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - математически оценить время исполнения подсчетом операций.
Рассмотрим алгоритм вычисления значения многочлена степени n
в заданной точке x
.
P n (x) = a n x n + a n-1 x n-1 + ... + a i x i + ... + a 1 x 1 + a 0
Алгоритм 1 - для каждого слагаемого, кроме a 0 возвести x в заданную степень последовательным умножением и затем домножить на коэффициент. Затем слагаемые сложить.
Вычисление i -го слагаемого(i=1..n ) требует i умножений. Значит, всего 1 + 2 + 3 + ... + n = n(n+1)/2 умножений. Кроме того, требуется n+1 сложение. Всего n(n+1)/2 + n + 1= n 2 /2 + 3n/2 + 1 операций.
Алгоритм 2
- вынесем x
-ы за скобки и перепишем многочлен в виде
P n (x) = a 0 + x(a 1 + x(a 2 + ... (a i + .. x(a n-1 + a n x)))
.
Например,
P 3 (x) = a 3 x 3 + a 2 x 2 + a 1 x 1 + a 0 = a 0 + x(a 1 + x(a 2 + a 3 x))
Будем вычислять выражение изнутри. Самая внутренняя скобка требует 1 умножение и 1 сложение. Ее значение используется для следующей скобки... И так, 1 умножение и 1 сложение на каждую скобку, которых.. n-1 штука. И еще после вычисления самой внешней скобки умножить на x и прибавить a 0 . Всего n умножений + n сложений = 2n операций.
Зачастую такая подробная оценка не требуется. Вместо нее приводят лишь асимптотическую скорость возрастания количества операций при увеличении n.
Функция f(n) = n 2 /2 + 3n/2 + 1 возрастает приблизительно как n 2 /2 (отбрасываем сравнительно медленно растущее слагаемое 3n/2+1 ). Константный множитель 1/2 также убираем и получаем асимптотическую оценку для алгоритма 1, которая обозначается специальным символом O(n 2) [читается как "О большое от эн квадрат"].
Это - верхняя оценка, т.е количество операций(а значит, и время работы) растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите на таблицу, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций.
n*log n |
|||
| 1 | 0 | 0 | 1 |
| 16 | 4 | 64 | 256 |
| 256 | 8 | 2,048 | 65,536 |
| 4,096 | 12 | 49,152 | 16,777,216 |
| 65,536 | 16 | 1,048,565 | 4,294,967,296 |
| 1,048,576 | 20 | 20,969,520 | 1,099,301,922,576 |
| 16,775,616 | 24 | 402,614,784 | 281,421,292,179,456 |
Если считать, что числа в таблице соответствуют микросекундам, то для задачи с n=1048576 элементами алгоритму с временем работы O(log n) потребуется 20 микросекунд, алгоритму со временем O(n) - 17 минут, а алгоритму с временем работы O(n 2) - более 12 дней... Теперь преимущество алгоритма 2 с оценкой O(n) перед алгоритмом 1 достаточно очевидно.
Наилучшей является оценка O(1) ... В этом случае время вообще не зависит от n , т.е постоянно при любом количестве элементов.
Таким образом, O() - "урезанная" оценка времени работы алгоритма, которую зачастую гораздо проще получить, чем точную формулу для количества операций.
При оценке за функцию берется количество операций, возрастающее быстрее всего.
То есть, если в программе одна функция, например, умножение, выполняется O(n)
раз, а сложение - O(n 2)
раз, то общая сложность программы - O(n 2)
, так как в конце концов при увеличении n
более быстрые (в определенное, константное
число раз) сложения станут выполнятся настолько часто, что будут влиять на быстродействие куда больше, нежели медленные, но редкие умножения. Символ O()
показывает исключительно
асимптотику!
При оценке O() константы не учитываются.
Пусть один алгоритм делает 2500n + 1000 операций, а другой - 2n+1. Оба они имеют оценку O(n)
, так как их время выполнения растет линейно.
В частности, если оба алгоритма, например, O(n*log n) , то это отнюдь не значит, что они одинаково эффективны. Первый может быть, скажем, в 1000 раз эффективнее. O() значит лишь то, что их время возрастает приблизительно как функция n*log n .
Другое следствие опускания константы - алгоритм со временем O(n 2) может работать значительно быстрее алгоритма O(n) при малых n ... За счет того, что реальное количество операций первого алгоритма может быть n 2 + 10n + 6 , а второго - 1000000n + 5 . Впрочем, второй алгоритм рано или поздно обгонит первый... n 2 растет куда быстрее 1000000n .
Основание логарифма внутри символа O()
не пишется.
Причина этого весьма проста. Пусть у нас есть O(log 2 n)
. Но log 2 n=log 3 n/log 3 2
, а log 3 2
, как и любую константу, асимптотика - символ О()
не учитывает. Таким образом, O(log 2 n)
= O(log 3 n)
.
К любому основанию мы можем перейти аналогично, а значит и писать его не имеет смысла.
Определение
O(g)
- множество функций f
, для которых существуют такие константы C
и N
, что |f(x)| <= C|g(x)|
для всех x>N
.
Запись f = O(g)
дословно обозначает, что f
принадлежит множеству O(g)
. При этом обратное выражение O(g) = f
не имеет смысла.
В частности, можно сказать, что f(n) = 50n принадлежит O(n 2) . Здесь мы имеем дело с неточной оценкой. Разумеется, f(n) <= 50n 2 при n>1 , однако более сильным утверждением было бы f(n) = O(n) , так как для C=50 и N=1 верно f(n) <= Cn, n>N .
Наряду с оценкой O(n)
используется оценка Ω(n)
[читается как "Омега большое от эн"]. Она обозначает нижнюю оценку роста функции. Например, пусть количество операций алгоритма описывает функция f(n) = Ω(n 2)
. Это значит, что даже в самом удачном случае будет произведено не менее порядка n 2
действий.
...В то время как оценка f(n) = O(n 3)
гарантирует, что в самом худшем случае действий будет порядка n 3
, не больше.
Также используется оценка Θ(n)
["Тэта от эн"], которая является гибридом O()
и Ω()
.
Θ(n 2)
является и верхней и нижней асимптотической оценкой одновременно -
всегда будет выполняться порядка n 2
операций. Оценка Θ()
существует только тогда, когда O()
и Ω()
совпадают и равна им.
Для рассмотренных выше алгоритмов вычисления многочлена найденные оценки являются одновременно O()
, Ω()
и Θ()
.
Если добавить к первому алгоритму проверки на x=0
в возведении в степень, то на самых удачных исходных данных(когда x=0
) имеем порядка n
проверок, 0 умножений и 1 сложение, что дает новую оценку Ω(n)
вкупе со старой O(n 2)
.
Как правило, основное внимание все же обращается на верхнюю оценку O() , поэтому, несмотря на "улучшение", алгоритм 2 остается предпочтительнее.
Итак, O() - асимптотическая оценка алгоритма на худших входных данных, Ω() - на лучших входных данных, Θ() - сокращенная запись одинаковых O() и Ω() .
Анализ алгоритмов –
Виды анализа
Наихудший случай: T(n)
Средний случай: T(n)
Асимптотическая оценка
O
f (n) = O(g(n)) Þ
($c > 0, n 0 >
O(g(n)) = {f (n) : $ c > 0, n 0 >
Пример: 2n 2 = O(n 3)
Сортировка слиянием
if(p < r) //1
 |
Дерево рекурсии: T(n) = 2*T(n/2) +cn, с –const, c>0
Методика оценки рекурсивных алгоритмов.
Метод итераций
На основании формулы T(n) записываем формулу для меньшего элемента, находящегося в правой части формулы для T(n).
Подставляем правую часть полученной формулы в исходную формулу
Выполняем первые два шага, пока не развернем формулу в ряд без функции T(n)
Оценим полученный ряд на основании арифметической или геометрической прогрессии
T(n)=T(n-1)+n, T(1)=1
T(n)=θ(g(n)), g(n)=?
T(n-1)=T(n-2)+(n-1)
T(n-2)=T(n-3)+(n-2)
T(n-3)+(n-2)+(n-1)+n=…
1+…(n-2)+(n-1)+n=
Дерево рекурсии - графический метод отображения подстановки соотношения самого в себя
T(n)=2T(n/2)+n 2
T(n/4) T(n/4) T(n/4) T(n/4)
(n/2) 2 (n/2) 2 log n (1/2)*n 2
(n/4) 2 (n/4) 2 (n/4) 2 (n/4) 2 (1/4)*n 2
Mетод подстановки
- Догадаться (предложить) о решении
- Проверить решение с помощью индукции
- Найти и подставить константы
T (n) = 2T (n/2) + n
T(n) = (n log n)
Посылка индукции: T(n) ≤ с * n* log n, c>0
Пусть эта оценка верна для n/2
T(n/2) ≤ c*(n/2)*log(n/2)
Подставим ее в исходную формулу для T(n)
T(n) ≤ 2*(c*(n/2)*log(n/2))+n ≤
c*n*log(n/2)+n =
c*n*log n - c*n*log 2 +n =
c*n*log n - c*n +n ≤
c*n*log n
c≥1, n ≥ 2
Основная теорема о рекуррентных оценках
T (n) = aT (n/b) + f (n), a ≥ 1, b > 1, f (n) − (f (n) > 0, n > n0)
Алгоритмы сортировки массивов за полиномиальное время
Сортировка - процесс перестановки объектов заданной
совокупности в определенном порядке (возрастающем
или убывающем).
Целью сортировки обычно является облегчение последующего
поиска элементов в отсортированном множестве.
Сортировка простыми вставками
void sort_by_insertion(key a , int N)
for (i=1; i < N; i++)
for (j=i-1; (j>=0)&& (x < a[j]); j--)
a = a[j];
Анализ сортировки простыми вставками
Количество сравнений:
С (N) = 1 + 2 + 3 + ... + N - 1 = (N *(N -1))/2= О (N 2)
Общее время: T(N) = θ(N 2)
Сортировка простым обменом. Метод пузырька.
void bubble_sort (key а , int N)
for (i=0; i for (j=N-l; j>i; j--) if (a > a[j]) { x = a [ j ] ; a [ j ] = a [ j -1] ; a [ j -1] = x; Анализ сортировки простым обменом Наихудший случай: упорядоченный в обратном порядке массив Количество сравнений: C(N) = (N - 1) + (N - 2) + ... + 1 = (N * (N-1))/2 = O(N 2)
Общее время: T(N) = θ(N 2)
Добавление
Node* _Add(Node *r, T s) r = new Node(s); else if(s < r->inf) r->left = _Add(r->left, s); r->right = _Add(r->right, s); Удаление элемента из дерева
Дерево Т с корнем n и ключом K. удалить из дерева Т узел с ключом K (если такой есть). Алгоритм: Если дерево T пусто, остановиться; Иначе сравнить K с ключом X корневого узла n. Если K>X, рекурсивно удалить K из правого поддерева Т; Если K Если K=X, то необходимо рассмотреть три случая. Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла; Если одного из детей нет, то значения полей ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m; Если оба ребёнка присутствуют, то найдём узел m, являющийся следующим за данным; скопируем данные (кроме ссылок на дочерние элементы) из m в n; рекурсивно удалим узел m. Элемент следующий за данным
Дано: дерево Т и ключ х Возвращаем указатель на следующий за х элемент или NULL, если элемент х последний в дереве. Алгоритм: Отдельно рассматривает два случая. Если правое поддерево вершины х не пусто, то следующий за х элемент – минимальный элемент в этом поддереве. Иначе, если правое поддерево вершины х пусто. Переходим от х вверх, пока не найдём вершину, являющуюся левым сыном своего родителя. Этот родитель (если он есть) и будет искомым элементом. Вставка узлов
Вставка нового ключа в АВЛ-дерево выполняется так же, как это делается в простых деревьях поиска: спускаемся вниз по дереву, выбирая правое или левое направление движения в зависимости от результата сравнения ключа в текущем узле и вставляемого ключа. Единственное отличие заключается в том, что при возвращении из рекурсии (т.е. после того, как ключ вставлен либо в правое, либо в левое поддерево) выполняется балансировка текущего узла. Возникающий при такой вставке дисбаланс в любом узле по пути движения не превышает двух, а значит применение вышеописанной функции балансировки является корректным. Удаление узлов
Для удалении вершины из АВЛ – дерева за основу взят алгоритм, который обычно применяется и при удалении узлов из стандартного двоичного дерева поиска. Находим узел p с заданным ключом k, в правом поддереве находим узел min с наименьшим ключом и заменяем удаляемый узел p на найденный узел min. При реализации возникает несколько вариантов. Прежде всего, если у найденный узел p не имеет правого поддерева, то по свойству АВЛ-дерева слева у этого узла может быть только один единственный дочерний узел (дерево высоты 1), либо узел p вообще лист. В обоих этих случаях надо просто удалить узел p и вернуть в качестве результата указатель на левый дочерний узел узла p. Пусть теперь правое поддерево у p есть. Находим минимальный ключ в этом поддереве. По свойству двоичного дерева поиска этот ключ находится в конце левой ветки, начиная от корня дерева. Применяем рекурсивную функцию findmin. функция removemin - удалением минимального элемента из заданного дерева. По свойству АВЛ-дерева у минимального элемента справа либо единственный узел, либо там пусто. В обоих случаях надо просто вернуть указатель на правый узел и по пути назад (при возвращении из рекурсии) выполнить балансировку. Хеш-таблицы, метод цепочек
Прямая адресация применяется для небольших множеств ключей. Требуется задать динамическое множество, каждый элемент которого имеет ключ из множества U = {0,1,..., m - 1}, где m не слишком велико, никакие два элемента не имеют одинаковых ключей. Для представления динамического множества используется массив (таблицу с прямой адресацией), Т , каждая позиция, или ячейка, которого соответствует ключу из пространства ключей U. Ячейка k указывает на элемент множества с ключом k. Если множество не содержит элемента с ключом k, то Т [k] = NULL. Операция поиска по ключу занимает время O(1)
Недостатки прямой адресации: Если пространство ключей U велико, хранение таблицы Т размером |U| непрактично, а то и вовсе невозможно - в зависимости от количества доступной памяти и размера пространства ключей Множество К реально сохраненных ключей может быть мало по сравнению с пространством ключей U, а в этом случае память, выделенная для таблицы Т, в основном расходуется напрасно. Хеш-функция – такая функция h, которая определяет местоположение элементов множества U в таблице T. При хешировании элемент с ключом k хранится в ячейке h(k), хеш-функция h используется для вычисления ячейки для данного ключа k. Функция h отображает пространство ключей U на ячейки хеш-таблицы Т [О..m - 1]: h: U → {0,1,..., m -1}. величина h (к) называется хеш-значением ключа к. Когда множество К хранящихся в словаре ключей гораздо меньше пространства возможных ключей U, хеш-таблица требует существенно меньше места, чем таблица с прямой адресацией. Цель хеш-функции состоит в том, чтобы уменьшить рабочий диапазон индексов массива, и вместо |U| значений можно обойтись всего лишь m значениями. Требования к памяти могут быть снижены до θ(|К|), при этом время поиска элемента в хеш-таблице остается равным О(1) - это граница среднего времени поиска, в то время как в случае таблицы с прямой адресацией эта граница справедлива для наихудшего случая. Коллизия – ситуация, когда два ключа отображаются в одну и ту же ячейку. Например, h(43) = h(89) = h(112) = k Метод цепочек:
Идея: Хранить элементы множества с одинаковым значением хэш-функции в виде списка. Анализ
Наихудший случай: если хэш-функция для всех элементов множество выдает одно и то же значение. Время доступа равно Θ(n), при |U|
= n.
Средний случай: для случая, когда значения хэш-функции равномерно распределены. Каждый ключ с равной вероятностью может попасть в любою ячейку таблицы, вне зависимости от того куда попали другие ключи. Пусть дана таблицы T, и в ней хранится n ключей. Тогда, а = n/m - среднее количество ключей в ячейках таблицы. Время поиска отсутствующего элемента – Θ(1 + α). Константное время на вычисления значения хэш-функции плюс время на проход списка до конца, т.к. средняя длина списка - α, то результат равен Θ(1) + Θ(α) = Θ(1 + α) Если количество ячеек таблицы пропорционально количеству элементов, хранящихся в ней, то n = O(m) и, следовательно, α = n/m = O(m)/m = O(1), а значит поиск элемента в хэш-таблице в среднем требует времени Θ(1). Операции Вставка элемента в таблицу Удаление также требуют времени O(1) Выбор хэш-функции
Ключи должны равномерно распределятся по всем ячейкам Закономерность распределения ключей хэш-функции не должна коррелировать с закономерностями данных. (Например, данные – это четные числа). Методы:
Метод деления Метод умножения Метод деления
h (k) = k mod m
Проблема маленького делителя m Пример №1. m = 2
и все ключи четные Þ нечетные ячейки не заполнены. Пример №2. m = 2 r
Þ хэш не зависит от бито в выше r
. Метод умножения
Пусть m
= 2 r , ключи являются w-битными словами. h(k) = (A k mod 2 w) >> (w - r),
где A mod 2 = 1 ∩ 2 w-1 < A< 2 w He следует выбирать A
близко к 2 w-1
и 2 w
Данный метод быстрее метода деления Метод умножения: пример
m = 8 = 2 3 , w = 7 Открытая адресация: поиск
Поиск – также последовательное исследование Успех, когда нашли значение Неудача, когда нашли пустую клетку или прошли всю таблицу. Стратегии исследования
Линейная - h(k, i) = (h′(k) + i) mod m Данная стратегия легко реализуется, однако подвержена проблеме первичной кластеризации, связанной с созданием длинной последова- тельности занятых ячеек, что увеличивает среднее время поиска. Квадратичная h(k, i) = (h′(k) + с 1 i+ с 2 i 2) mod m где h′(k) – обычная хэш-функция Двойное хеширование – h(k,i) = (h 1 (k) + i h 2 (k)) mod m.
Двойное хеширование Этот метод даёт отличные результаты, но h 2 (k) должен быть взаимно простым с m. Этого можно добиться: используя в качестве m степени двойки и сделав так, чтобы h 2 (k) выдавала только нечётные числа m = 2 r иh 2 (k)
– нечетная. m
- простое число, значения h 2 – целые положительные числа, меньшие m
Для простого m можно установить
h1(k)=k mod m
h2(k)=1+(k mod m’)
m’ меньше m (m’
= m-1 или m-2)
Открытая адресация: пример вставки
Пусть дана таблица A: Двойное хеширование h2(k)=1+(k mod 11) Куда будет встроен элемент? Анализ открытой адресации
Дополнительное допущение для равномерного хеширования: каждый ключ может равновероятно получить любую из m! перестановок последовательностей исследования таблицы независимо от других ключей. Поиск отсутствующего элемента Число проб при успешном поиске Открытой адресации
а < 1 - const Þ O(1)
Как же себя ведет а:
Таблица заполнена 50% Þ2 исследования Таблица заполнена на 90% Þ 10 исследований Таблица заполнена на 100% Þ m исследований Принцип жадного выбора
Говорят, что к оптимизационной задаче применим принцип жадного выбора
, если последовательность локально оптимальных выборов даёт глобально оптимальное решение. В типичном случае доказательство оптимальности следует такой схеме: Доказывается, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не хуже первого. Показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной. Рассуждение завершается по индукции. Оптимальность для подзадач
Говорят, что задача обладает свойством оптимальности для подзадач
, если оптимальное решение задачи содержит в себе оптимальные решения для всех её подзадач. Построение кода Хаффмена
Любое сообщение состоит из последовательности символов некоторого алфавита. Зачастую для экономии памяти, для увеличения скорости передачи информации возникает задача сжатия информации. В этом случае используются специальные методы кодирования символов. К таким относятся коды Хаффмена, которые дают сжатие от 20% до 90% в зависимости от типа информации. Алгоритм Хаффмена находит оптимальные коды символов исходя из частоты использования символов в сжимаемом тексте. Алгоритм Хаффмена является примером жадного алгоритма. Пусть в файле длины 100000 символы известны частоты символов: Нужно построить двоичный код, в котором каждый символ представляется в виде конечной последовательности битов, называемой кодовым словом. При использовании равномерного кода, в котором все кодовые слова имеют одинаковую длину, на каждый символ тратится минимум три бита и на весь файл уйдет 300000 битов. Неравномерный код будет экономнее, если часто встречающиеся символы закодировать короткими последовательностями битов, а редко встречающиеся символы – длинными. При кодировке на весь файл уйдет (45*1 + 13*3 + 12*3 + 16*3 + 9*4 + 5*4)*1000 = 224000. То есть, неравномерный код дает около 25% экономии. Префиксные коды
Рассмотрим коды, в которых для каждой из двух последовательностей битов, представляющих различные символы, ни одна не является префиксом другой. Такие коды называются префиксными кодами. При кодировании каждый символ заменяется на свой код. Например, строка abc выглядит как 0101100. Для префиксного кода декодирование однозначно и выполняется слева направо. Первый символ текста, закодированного префиксным кодом, определяется однозначно, так как его кодовое слово не может быть началом какого-либо другого символа. Определив этот символ и отбросив его кодовое слово, повторяем процесс для оставшихся битов и так далее. Для эффективной реализации декодирования нужно хранить информацию о коде в удобной форме. Одна из возможностей – представить код в виде кодового двоичного дерева
, листья которого соответствуют кодируемым символам. При этом путь от корня до кодируемого символа определяет кодирующую последовательность битов: переход по дереву налево дает 0, а переход направо – 1. Во внутренних узлах указана сумма частот для листьев соответствующего поддерева. Оптимальному для данного файла коду всегда соответствует двоичное дерево, в котором всякая вершина, не являющаяся листом, имеет двух сыновей. Равномерный код не является оптимальным, так как в соответствующем ему дереве есть вершина с одним сыном. Дерево оптимального префиксного кода для файла, в котором используются все символы из некоторого множества С и только они содержат ровно | С | листьев по одному на каждый символ и ровно | С | - 1 узлов, не являющихся листьями. Зная дерево Т, соответствующее префиксному коду, легко найти количество битов, необходимое для кодирования файла. Для каждого символа с из алфавита С, пусть f [c] означает число его вхождений в файл, а dT (c) – глубину соответствующего ему листа и, следовательно, длину последовательности битов, кодирующей с. Тогда для кодирования файла потребуется: Эта величина называется стоимостью дерева Т. Необходимо минимизировать эту величину. Хаффмен
предложил жадный алгоритм, который строит оптимальный префиксный код. Алгоритм строит дерево Т, соответствующее оптимальному коду снизу вверх, начиная с множества из | С | листьев и делая | С | - 1 слияний. Для каждого символа задана его частота f [c]. Для нахождения двух объектов для слияния используется очередь с приоритетами Q, использующая частоты f в качестве приоритетов – сливаются два объекта с наименьшими частотами. В результате слияния получается новый объект (внутренняя вершина), частота которого считается равной сумме частот двух сливаемых объектов. Эта вершина заносится в очередь. Huffman (C
)
1. n ←│C│ │C
│- мощность С 2. Q ← C
Q – очередь с приоритетами 3. for
i ← 1 to
n-1 4. do
z ← Create_Node
() z – узел, состоящий из полей f, left, right 5. x ← left [z] ← Dequeue
(Q) 6. y ← right [z] ← Dequeue
(Q) 7. f[z] ← f[x] + f[y] 8. Enqueue
(Q, z) 9. return Dequeue
(Q) вернуть корень дерева Оценка
Очередь реализована в виде двоичной кучи. Создать очередь можно за O(n). Алгоритм состоит из цикла, который выполняется n-1 раз. Каждая операция с очередью выполняется за O(log n). Общее время работы O(n log n). Проблема построения сети
Области возникновения: коммуникационные и дорожные сети. Дано:
множество узлов сети (хосты, города). Необходимо:
построение сети с наименьшим общим весом ребер (длина сетевых кабелей, длина дорог). Графовая модель:
узлы сети являются узлами графа, E = V 2
, нам известны веса всех ребер. Результат:
свободное дерево. Подход к поиску МОД
Строим дерево A путем добавления по одному ребру, и перед каждой итерацией текущее дерево является подмножеством некоторого МОД. На каждом шаге алгоритма мы определяем ребро (u, v), которое можно добавить к А без нарушения этого свойства. Мы назовем такое ребро безопасным GenericMST(G, w) 2 while A не является МОД 3 do Найти безопасное для A ребро (u, v) 4 A ← A U {(u, v)} ____________________________________________________________________________ Классификация ребер
1. Ребра деревьев
(tree edges) - это ребра графа G. Ребро (u, v) является ребром дерева, если при исследовании этого ребра открыта вершина v. 2. Обратные ребра
(back edges) - это ребра (u,v), соединяющие вершину u с ее предком v в дереве поиска в глубину. Ребра-циклы, которые могут встречаться в ориентированных графах, рассматриваются как обратные ребра. 3. Прямые ребра
(forward edges) - это ребра (u,v), не являющиеся ребрами дерева и соединяющие вершину u с ее потомком v в дереве поиска в глубину. 4. Перекрестные ребра
(cross edges) - все остальные ребра графа. Они могут соединять вершины одного и того же дерева поиска в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях. Алгоритм DFS можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея заключается в том, что каждое ребро (u, v) можно классифицировать при помощи цвета вершины v при пер- первом его исследовании (правда, при этом не различаются прямые и перекрестные ребра). Первый случай следует непосредственно из определения алгоритма. Рассматривая второй случай, заметим, что серые вершины всегда образуют линейную цепочку потомков, соответствующую стеку активных вызовов процедуры DFS_Visit; количество серых вершин на единицу больше глубины последней открытой вершины в дереве поиска в глубину. Исследование всегда начинается от самой глубокой серой вершины, так что ребро, которое достигает другой серой вершины, достигает предка исходной вершины. В третьем случае мы имеем дело с остальными ребрами, не подпадающими под первый или второй случай. Можно показать, что ребро (u, v) является прямым, если d [u] < d [v], и перекрестным, если d [u] > d [v] ___________________________________________________________________________ Топологическая сортировка
В графе предшествования
каждое ребро (u, v) означает, что u предшествует v Топологическая сортировка
графа есть построение последовательности а, где для всех a i и a j выполняется $(а i ,а j) Þ i < j. Топологическая сортировка (topological sort) ориентированного ациклического графа G = (V, Е) представляет собой такое линейное упорядочение всех его вершин, что если граф G содержит ребро (u,v) то u при таком упорядочении располагается до v (если граф не является ацикличным, такая сортировка невозможна). Топологическую сортировку графа можно рассматривать как такое упорядочение его вершин вдоль горизонтальной линии, что все ребра направлены слева направо. Отсортированная последовательность: C2, C6, C7, C1, C3, C4, C5, C8 for each(u in V) color[u] = white; // initialize L = new linked_list; // L is an empty linked list for each (u in V) if (color[u] == white) TopVisit(u); return L; // L gives final order TopVisit(u) { // start a search at u color[u] = gray; // mark u visited for each (v in Adj(u)) if (color[v] == white) TopVisit(v); Append u to the front of L; // on finishing u add to list T (n) = Θ(V + E)
Процедуры
Create - Set (u)
- создать множество из одной вершины u.
Find - Set (u)
- найти множество, которому принадлежит вершина u
возвращает, в каком множестве
находится указанный элемент. На самом деле при этом возвращается один из элементов множества (называемый представителем
или лидером
). Этот представитель выбирается в каждом множестве самой структурой данных (и может меняться с течением времени, а именно, после вызовов Union
). Если вызов Find - Set для каких-то двух элементов вернул одно и то же значение, то это означает, что эти элементы находятся в одном и том же множестве, а в противном случае - в разных множествах. Union (u,v)
- объединить множества, которые содержат вершины u
и v
Множества элементов будем хранить в виде деревьев
: одно дерево соответствует одному множеству. Корень дерева - это представитель (лидер) множества. При реализации это означает, что мы заводим массив parent
, в котором для каждого элемента мы храним ссылку на его предка в дерева. Для корней деревьев будем считать, что их предок - они сами (т.е. ссылка зацикливается в этом месте). Чтобы создать новый элемент (операция Create - Set
), мы просто создаём дерево с корнем в вершине v , отмечая, что её предок - это она сама. Чтобы объединить два множества (операция Union(a,b)
), мы сначала найдём лидеров множества, в котором находится a, и множества, в котором находится b. Если лидеры совпали, то ничего не делаем - это значит, что множества и так уже были объединены. В противном случае можно просто указать, что предок вершины b равен f (или наоборот) - тем самым присоединив одно дерево к другому. Наконец, реализация операции поиска лидера (Find - Set(v)
) проста: мы поднимаемся по предкам от вершины v , пока не дойдём до корня, т.е. пока ссылка на предка не ведёт в себя. Эту операцию удобнее реализовать рекурсивно. Эвристика сжатия пути
Эта эвристика предназначена для ускорения работы Find - Set()
. Она заключается в том, что когда после вызова Find - Set(v)
мы найдём искомого лидера p
множества, то запомним, что у вершины v
и всех пройденных по пути вершин - именно этот лидер p
. Проще всего это сделать, перенаправив их parent
на эту вершину p
. Таким образом, у массива предков parent
смысл несколько меняется: теперь это сжатый массив предков
, т.е. для каждой вершины там может храниться не непосредственный предок, а предок предка, предок предка предка, и т.д. С другой стороны, понятно, что нельзя сделать, чтобы эти указатели parent
всегда указывали на лидера: иначе при выполнении операции Union
пришлось бы обновлять лидеров у O(n)
элементов. Таким образом, к массиву parent
следует подходить именно как к массиву предков, возможно, частично сжатому. Применение эвристики сжатия пути позволяет достичь логарифмическую асимптотику
: на один запрос в среднем Анализ
Инициализация – O(V) Цикл выполняется V раз и каждая операция extractMin выполняется за - O(logV) раз, всего O(V logV) раз Цикл for выполняется O(E) раз, decreaseKey - за время O(logV) . Общее время работы - O(V log V +E logV)= O(E logV) Свойство кратчайшего пути
Пусть p = (v 1 , v 2 ..... v k)
- кратчайший путь из вершины v 1 к вершине v k
в заданном взвешенном ориентированном графе G = (У. Е)
с весовой функцией w: Е → R
a p ij = (v i , v i+1 .....v j)
- частичный путь пути p, который проходит из вершины v i
к вершине v j
для произвольных i и j (1 ≤ i < j ≤ k).
Тогдa p ij
– кратчайший путь из вершины v i
к v i
Dijkstra(G, w, s) { for each (u in V) { // initialization d [u] = +infinity color [u] = white d[s] =0 // dist to source is 0 Q = new PriQueue(V) // put all vertices in Q while (Q.nonEmpty()) { // until all vertices processed u = Q.extractMin(} // select u closest to s for each (v in Adj[u]) { if (d[u] + w(u,v) < d[v]) { // Relax(u,v) d [v] = d [u] + w(u,v) Q.decreaseKey(v, d[v]) color [u] = black Оценка сложности
Алгоритм Беллмана-Форда завершает свою работу в течение времени O(V*E)
, поскольку инициализация в строке 1 занимает время O(V), на каждый из |V| - 1 проходов по ребрам в строках 2-4 требуется время в O(E), а на выполнение цикла for в строках 5-7 - время O(Е). . Асимптотическая оценка алгоритма
Анализ алгоритмов –
теоретическое исследование производительности компьютерных программ и потребляемых ими ресурсов. Быстродействие – время работы алгоритма, в зависимости от объема входных данных. Определяется функцией Т(n), где n – объем входных данных Виды анализа
Наихудший случай: T(n)
– максимальное время для любых входных данный размера n. Средний случай: T(n)
– ожидаемое время для любых входных данных размера n. Наилучший случай – минимальное время работы. Асимптотическая оценка
O
- нотация: асимптотическая верхняя граница f (n) = O(g(n)) Þ
($c > 0, n 0 > 0 Þ 0 ≤ f (n) ≤ c · g(n), n ≥ n 0)
O(g(n)) = {f (n) : $ c > 0, n 0 > 0 Þ 0 ≤ f (n) ≤ c · g(n), n ≥ n 0 }
Пример: 2n 2 = O(n 3)
Рекурсивные алгоритмы, построение асимптотической оценки. Пример
Сортировка слиянием sort(А,p,r) //p - начало массива, r – конец массива T(n) if(p < r) //1 q=(p + r)/2; //Вычисляем середину массива 1 sort(А,p,q); //сортируем левую часть T(n/2) sort(А,q+1,r); //сортируем правую часть T(n/2) merge(p,q,r); //сливаем два массива в один n Для теоретического анализа принципиальна
не конкретная функция, описывающая
зависимость времени выполнения от
количества входных данных, а порядок
ее роста для больших N. Первоочередный
интересующий разработчика алгоритма
вопрос - это совсем не вычисление
конкретного промежутка времени,
необходимого для выполнения задачи на
выбранном наборе входных данных, для
чего более подходит измерение. Ключевые
вопросы состоят, во-первых, в определении
возможности компьютерного решения за
конечное приемлемое время в принципе,
во-вторых в сравнении альтернатив и
отбрасывании неподходящих алгоритмов
из рассмотрения еще до того, как затрачены
усилия на достижение их полноценной
качественной реализации. Иначе говоря, определяющую роль играет
асимптотическая оценка
вычислительной
сложности алгоритма. Возьмем предел от
рассмотренного выше соотношения для
алгоритма пузырьковой сортировки, при
количестве входных данных N, стремящемся
к бесконечности: При предельной оценке младшие степени
отбрасываются, поскольку старшие степени
доминируют. Таким образом, время
выполнения алгоритма пузырьковой
сортировки имеет квадратичную зависимость
от объема входных данных. В общем виде, время выполнения любого
алгоритма можно представить следующим
образом: При изучении свойств и сравнении
алгоритмов можно отбросить константный
множитель, поскольку при достаточно
больших N именно порядок роста функции
является определяющим фактором. Это
легко объяснить на примере. Предположим
имеется 2 альтернативных алгоритма, при
этом первый имеет квадратичный порядок
роста, а второй - описывается линейной
функцией. Также допустим, что реализация
первого алгоритма близка к оптимальной,
а программа выполняется на современном
компьютере. В то же время, реализация
второго алгоритма далека от блестящей
и выполняется на устаревшем компьютере.
Такой дисбаланс внешних условий можно
смоделировать при помощи разницы в
константных множителях (пусть,,
а).
При небольших N, например, при 5 данных,
время выполнения первого алгоритма
будет меньшим времени второго: Однако, с возрастанием количества
входных данных, второй алгоритм,
обладающих лучшей вычислительной
сложностью, превзойдет первый, несмотря
на все неудачные факторы: Каковы бы ни были значения константных
множителей, когда вычислительная
сложность одного алгоритма лучше
вычислительной сложности другого,
всегда существует некоторый переломный
объем входных данных
,
начиная с которого именно порядок роста
времени выполнения алгоритма становится
доминирующим фактором. Для аналитических рассуждений об
асимптотических оценках вычислительной
сложности алгоритмов в литературе
используются сразу несколько математических
нотаций - O-оценка,
-оценка
и-оценка. Оценка
представляет собой сравнение с бесконечным
множеством функций с одинаковым порядком
роста,
отличающихся на константный множитель.
Функцияпринадлежит множеству,
если имеются такие константыи,
которые при достаточно больших N сверху
и снизу ограничивают функцию, описывающую
скорость анализируемого алгоритма.
Таким образом, выполняется следующее
соотношение: O-оценка является подмножеством
-оценки,
ограничивающим функцию анализируемого
алгоритма только сверху. Иначе говоря,
О-оценка асимптотически описывает
худший случай для анализируемого
алгоритма. Такая оценка используется
при анализе наиболее часто. Существенно
реже используется-оценка,
ограничивающая функцию анализируемого
алгоритма снизу (лучший случай). Среди типично встречающихся асимптотических
оценок вычислительной сложности
алгоритмов распространенными являются
следующие функции: линейная O(N) (время пропорционально
увеличению данных); квадратичная O(N 2); полиномиальная сложность O(N M),
в частности, кубическая O(N 3); экспоненциальная сложность O(2 N); факториальная сложность O(N!); логаримфическая сложность O(log(N))
(подразумевают логарифм по основанию
2); линейно-логарифмическая сложность O(N
* log(N)) ; константная вычислительная сложность
O(1) (время не зависит от количества
данных). Этот список не исключает появления
других функций, однако здесь перечислено
подавляющее большинство встречающихся
на практике случаев. Указанные функции
можно упорядочить следующим образом
от наиболее к наименее эффективным: Вычислительную сложность разрабатываемых
алгоритмов следует максимально
ограничивать, насколько это является
возможным. Соотношение между данными
оценками можно ощутить, представив
количество выполненных инструкций на
конкретных примерах, скажем при N=5, 10,
25, 100 и 500 (положим, что константные
коэффициенты одинаковы для упрощения
понимания). При таком объеме данных
получим следующие показатели: очень много очень много очень много очень много очень много Константная вычислительная сложность
является идеальным случаем, часто
алгоритмов с такой сложностью для
решения задач просто не существует.
Логарифмическая функция также растет
относительно медленно. Линейная и
линейно-логарифмические функции растут
с приемлемой скоростью. Остальные
функции растут заметно быстрее. Если программа относится к
научно-исследовательским, предельно
допустимой сложностью является
полиномиальная, в частности, кубическая
.
Алгоритмы с более высокой вычислительной
сложностью имеют применение только для
малых значений N, в противном случае
задачи не имеют компьютерного решения
с достижимыми вычислительными затратами. В тоже время, в коммерческом секторе
программного обеспечения, где важным
является не только достижимость
результата вообще, но и приемлемое время
ожидания пользователя, редко применяются
алгоритмы, сложность которых превышает
линейно-логарифмическую
. Поверхностная
оценка вычислительной сложности
В классической литературе о построении
и анализе алгоритмов существенное
внимание уделяется строгим математическим
выкладкам, аналитически выводящим и
доказывающим гипотезы о вычислительной
сложности конкретных алгоритмов.
Практикующие программисты уделяют
данному процессу намного меньше внимания,
избегая рассуждений в формализованном
строгом стиле математиков. Все же, если
программный код, реализующий тот или
иной алгоритм, не слишком запутан,
представляется возможным высказать
некоторую близкую к корректной гипотезу
о вычислительной сложности лишь по
общей структуре программного кода. Ниже приведено несколько подсказок для
поверхностной оценки вычислительной
сложности “”на глаз” без строгого
аналитического подхода. Все элементарные инструкции - вычисление
выражений, присвоение переменных,
ввод-вывод, возврат значения - следует
воспринимать как простейшие блоки,
обладающие константной вычислительной
сложностью O(1). Вычислительная сложность последовательности
инструкций равна максимальной сложности
входящих в нее инструкций. Если нет никаких специальных сведений
о вероятности срабатывания условных
переходов, то все возможные условные
переходы, в том числе неявные (опущенные
ветки else, default), следует считать
равновероятными. Сложность каждого
блока инструкций оценивается отдельно,
а затем выбирается максимальная из
них, что и становится результатом оценки
для условной конструкции в целом. Если инструкция находится в теле цикла,
количество итераций которого зависит
от N, то вычислительная сложность
инструкции умножается на линейную
функцию. Вычислительная сложность двух циклов,
зависящих от N, вложенных друг в друга,
скорее всего описывается квадратичной
функцией. Соответственно, вложенность
из 3 уровней соответствует кубической
сложности. Если алгоритм разбивает набор входных
данных на части, а затем обрабатывает
их отдельно тем же самым алгоритмом
рекурсивно - вычислительная сложность
является логарифмической. Многие алгоритмы являются рекурсивными,
т.е. вызывают сами себя с другими
аргументами. При этом, для выхода из
рекурсии всегда должно существовать
некоторое “условие выхода” - значения
аргументов, при которых рекурсия
разрывается и выполняется некоторое
элементарное действие. Простейшим
примером может послужить функция
вычисления факториала: int
factorial
(int
_x) if
(_x < 1) return
0; else
if
(_x == 1) return
1; return
_x
* factorial(_x - 1); Первые два разветвления основного
условия являются элементарными
инструкциями, их вычислительная сложность
оценивается как O(1). Что же касается
последней ветки, сложность описывается,
так называемым, рекуррентным
соотношением
: Для получения оценки вычислительной
сложности рекуррентные соотношения
необходимо раскрывать аналитическим
способом. Подставляя ответы в указанную
формулу сложности для факториала шаг
за шагом, получим линейную зависимость.
h(51) = h(49) = h(63) = i
