Меры временной сложности алгоритмов. Оценки в среднем и в худшем случаях. Амортизированное время

И 4 на одном листе

Лексикографическая сортировка последовательностей одинаковой длины

 

Лексикографическая сортировкаДанный метод является обобщением сортировки подсчётом, при условии, что ключи задаются векторами конечной размерности. Имеется массив из n чисел от 0 до (2 в степени k), каждое из которых рассматривается как k-битовое слово(пример реализации приведен во введении). При реализации поразрядной сортировки существенным образом использует свойство устойчивости. Алгоритм может быть применен к векторам, заданным в m-ичной системе счисления. Если максимальная длина вектора равна d , и элементы этих векторов выбраны из алфавита мощности m , то сложность алгоритма поразрядной сортировки равна

O(d(n + m)) . При условии, что вектора имеют постоянную длину, не зависящую от n , и m = O(n) имеем линейный алгоритм сортировки.

Лексикографическая сортировка может быть обобщена на случай, когда ключи имеют переменную длину и их необходимо разместить в лексикографическом порядке. Пусть £ - отношение порядка, заданное на множестве S , | S |= m . Лексикографическим порядком называется такое продолжение отношения £ на кортежи элементов из S , при котором ( , ,..., ) ( , ,..., ) 1 2 p 1 2 q a a a £ b b b , если выполняется одно из условий:

1) существует целое число j , что j j a < b и для всех i < j выполняется i i a = b ;

2) p £ q и i i a = b при 1£ i £ p .

Лексикографически упорядоченными являются телефонные справочники, различные словари. Многократно разбивая последовательность на m частей (организованных в виде линейных списков), помещая на t шаге все элементы с одним и тем же значением в ( n - t +1) позиции в один список, а затем объединяя списки с учетом отношения £ , получаем алгоритм лексикографической сортировки последовательностей разной длины[2].

 

Задача «Объединить-Найти». Решение задачи для построения связной сети методом «Разделяй и властвуй»

Решение задачи построения связной сети методом взвешенного быстрого объединения со сжатием пути.

Программа 3.4. Решение задачи связности методом взвешенного быстрого объединения со сжатием пути. В предыдущем алгоритме нам удалось так организовать вычисления, что высота деревьев, представляющих множества, ограничена логарифмом от N. Если бы удалось ограничить высоту этих деревьев константой, то получили бы константное время для операции «поиск». Но это выглядит совсем не реалистично... однако встроить в программу преобразование, существенно уменьшающее высоту деревьев всегда можно. Вопрос только в том, окупятся ли затраты на это преобразование.

Рассмотрим совсем простое преобразование. При выполнении операции «найти» приходится проходить путь от вершины, которую ищем, до корня дерева:

t:=p; WHILE t<>id[t] DO t:=id[t];

Проходя этот путь, проведем реструктуризацию дерева:

t:=p; WHILE t<>id[t] DO BEGIN id[t]:= id[id[t]]; t:=id[t] END;

Суть приема не в том, что мы теперь в теле цикла выполняем два перехода за раз, а в том, что проходя путь: (i0®i1®i2®i3®i4®i5®i6®i7®i8®i9®...)

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

(i0®i2®i4®i6®i8®...)

(i1®i2®i4®i6®i8®...)

(i3®i4®i6®i8®...)

...

 

Продолжение 4

Затраты на эту реструктуризацию не значимые, а если в будущем нам придется выполнять операцию «найти» для этих элементов, то она будет выполняться в два раза быстрее. // Инициализируем id семейством всех одноэлементных множеств,

// а sz – соответственно объемами этих множеств.

FOR i:=0 TO N-1 DO BEGIN id[i]:=i; sz[i]:=1 END;

// Приступаем к обработке входной последовательности:

WHILE NOT EOF(input) DO BEGIN READLN(p,q);

t:=p;WHILE t<>id[t] DO BEGIN id[t]:=id[id[t]];t:=id[t] END;

j:=q;WHILE j<>id[j] DO BEGIN id[j]:=id[id[j]];j:=id[j] END;

IF t<>j THEN {p,q – пока не связаны} BEGIN WRITELN(p,q);

// А теперь пополним текущую «общую картину о связности»:

IF sz[t]<sz[j] THEN // множество t меньше множества j

// union(j,t): j:=jÈt: к большему j подсоединяем меньшее t

BEGIN id[t]:=j; sz[j]:=sz[j]+sz[t] END

ELSE // множество j меньше множества t

// union(t,j): t:=tÈj: к большему t подсоединяем меньшее j

8 Двойственность одна из фундаментальных связей между проблемами, которая в математике всегда фиксируется, изучается и используется...

BEGIN id[j]:=t; sz[t]:=sz[t]+sz[j] END

END

END

Экспериментальное тестирование этой программы на длинных входных последовательностях покажет почти линейную зависимость времени работы от длины входа. И это не случайно. Для варианта полного сжатия, когда при реструктуризации дерева все вершины пути, проходимого операцией «найти», привязываются к корню,

доказана почти линейная оценка времени в худшем:

§ Пусть F(0)=1, F(i)=2F(i-1) для i>0. Функция F растет очень быстро (возрастающее- многократная экспонента).

§ Функция G(n), инверсия функции F – наименьшее k, для которого F(k)≥n. Функция G растет очень медленно (возрастающее-многократный логарифм).

Верхняя оценка времени работы такого алгоритма в худшем на (достаточно длинных) входах длины M равна C*M*G(M) для подходящей константы C 9.

Подведем некоторые итоги. В этом разделе мы руководствовались следующей стратегией в изложении материала о разработке алгоритмов решения задач:

§ Построение модели задачи, описание объектов задачи и основных операций с этими объектами. Выбор алгоритма решения задачи и описание его в терминах основных операций над основными объектами модели задачи.

§ Выбор структур данных – способа представления объектов задачи, и соответствующего способа реализации операций с так представленными объектами. Уточнение алгоритма в терминах выбранного способа реализации модели задачи.

§ Анализ алгоритма, оценка ресурсов времени и памяти им расходуемых, выявление «узких» мест...

Осознанное абстрагирование от способа представления объектов задачи (абстракция данных) и способа реализации операций с этими объектами (процедурная абстракция) приводит нас к понятию абстрактный тип данных, к соответствующей технологии разработки алгоритмов решения задач и их программной реализации.

 

Меры временной сложности алгоритмов. Оценки в среднем и в худшем случаях. Амортизированное время

Наихудшее и среднее время работы.

Характер (и диапазон) изменения времени работы алгоритма обычно зависит от «объема» входных данных. Причем смысл понятия «объем» может зависеть от вида задачи, например, для задачи «Найти n-е простое число» видимо значение n является реалистичным смыслом для понятия «объем», а для задачи «Вычислить сумму n чисел» важны скорее не значения слагаемых, а их количество n. Оценивая время работы алгоритма некоторой функцией T(n) от «объема» входа, мы получаем возможность сравнивать алгоритмы, отвлекаясь от разнообразия входов «объема» n, сравнивать их по скорости роста их функции T(n). При этом возникают вопросы, как и для каких конкретно входных данных производить сравнение. Выбор 10 А это напрямую связано с анализом алгоритма решения задачи

 

конкретной функции T(n) сильно зависит от решаемой проблемы, от возможностей анализа исходных данных. Рассмотрим некоторые наиболее часто используемые определения этой функции.

§ Время в наихудшем случае. Определим T(n) как время работы на самом плохом входе, на котором алгоритм затрачивает максимальное время среди всех входов «объема» n. Такое определение T(n) акцентирует внимание на гарантиях – на любой вход «объема» n алгоритм затратит не более чем T(n) времени.

§ Время работы на самых хороших входах видимо мало чего говорит о самой задаче. Обычно разные программы решения одной и той же задачи показывают наилучшее время на разных входах, и в этих случаях более или менее ясно, как переориентировать программу с одних наилучших входов на другие без существенного изменения существа программы.

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

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

Другой вариант трактовать функцию T(n) – как время работы в среднем по всем входам «объема» n. При таком определении T(n) оценка дает меньше гарантий - может поступить вход, на котором программа будет работать дольше чем T(n). Но зато такая оценка будет более реалистичной, если конечно базовое распределение вероятностей входов действительно реалистично соответствует практике

применения программы.

Специфическим вариантом времени в среднем является амортизированное время. При амортизационном анализе (amortized analysis) время, требуемое для выполнения последовательности операций над структурой данных, усредняется по всем выполняемым операциям. Этот анализ можно использовать, например, чтобы показать, что даже если одна из операций последовательности является

дорогостоящей, то при усреднении по всей последовательности средняя стоимость операций будет небольшой. При амортизационном анализе гарантируется средняя производительность операций в наихудшем случае, но с усреднением по последовательностям (допустимых) операций.