Главная | Обратная связь | Поможем написать вашу работу!

Лемма Для определения того, связаны ли два из N объектов, алгоритму взвешенного быстрого объединения требуется отследить максимум lg N указателей.

При объединении набора, состоящего из i узлов, с набором, состоящим из j узлов, при количество указателей, которые должны отслеживаться в меньшем наборе, увеличивается на 1, но теперь узлы находятся в наборе размера i+j, и, следовательно, свойство остается справедливым, поскольку 1 + lg i = lg(2i) =
lg(i + i) < lg(i + j).

А это уже гарантия совсем неплохого времени выполнения операции «найти» при очень хорошем времени выполнения операции «объединить».

Кстати, идею взвешенного объединения (вливания меньшего множества в большее) можно применить и для алгоритма быстрого поиска. Тогда существенно сократится количество необходимых корректировок при вливании множества, содержащего id[i], в другое множество. Но это не улучшит алгоритм, потому что эти элементы id[i] надо еще найти. Но если иметь и поддерживать связный линейный список элементов для каждого множества (как в задаче о лексикографической сортировке), то алгоритм можно «дожать»... Получим двойственный алгоритм с аналогичными общими характеристиками, но с быстрым поиском и логарифмическим объединением [8].

Итого, мы получили алгоритм, который на последовательности из M пар связности на N элементах, затрачивает примерно M*log₂(N) времени в худшем случае. Это существенно лучше, чем предыдущие алгоритмы, для которых оценка по времени в худшем примерно M*N. Можно ли существенно улучить этот алгоритм? Оказывается можно.

Программа 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;

Суть приема не в том, что мы теперь в теле цикла выполняем два перехода за раз, а в том, что проходя путь:

(i₀®i₁®i₂®i₃®i₄®i₅®i₆®i₇®i₈®i₉®...)

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

(i₀®i₂®i₄®i₆®i₈®...)

(i₁®i₂®i₄®i₆®i₈®...)

(i₃®i₄®i₆®i₈®...)

...

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

// Инициализируем 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

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

END

Рис. 6. Сжатие пути

В общем виде, алгоритмы сжатия для эффективного поиска осуществляют следующее преобразование

Рис. 7. Реализация поиска со сжатием пути

Экспериментальное тестирование этой программы на длинных входных последовательностях покажет почти линейную зависимость времени работы от длины входа[3].

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

§ Введем функцию F (Функция Аккермана):

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

Рис. 8 Несколько значений функции F

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

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

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

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

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

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

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

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

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

Разработка эффективного алгоритма приносит моральное удовлетворение и прямо окупается на практике. Как видно на примере решения задачи связности, просто сформулированная задача может приводить к изучению множества алгоритмов, которые не только полезны и интересны, но и представляют увлекательную и сложную для понимания задачу.

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

Основные понятия.

1.1. Основы анализа алгоритмов. [4 ч.1, гл.17, гл.34.]

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

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

С одной стороны, дело обстоит действительно так, и нет оснований это оспаривать, но с другой стороны, все это только подчеркивает, что всеобъемлющий анализ алгоритмов – является очень сложной проблемой. А потому даже для ориентировочной оценки качества алгоритма необходимо понимать, как это можно сделать, если конечно мы хотим иметь достаточно весомые основания объективности и реалистичности этой оценки...

Обычно время работы программы зависит от входных данных, а потому экспериментальное тестирование программы с целью оценить время ее работы тоже требует специального анализа для обоснованного подбора серии тестов.[10] Хорошо известно, что обычно и плохой программе можно подобрать вход, на котором она хорошо работает, и хорошей программе можно подобрать вход, на котором она плохо работает, по крайней мере - не лучше других. К тому же экспериментальное тестирование возможно и покажется нам достаточным, если оно покажет приемлемые характеристики программы, а если нет... Сказанное ни в коей мере не принижает роль экспериментального тестирования в оценке характеристик программы, сказанное только акцентирует внимание на том, что обоснование экспериментальных оценок – не менее сложная проблема, чем в случае аналитического подхода к оценке характеристик программы, если конечно мы хотим иметь достаточно весомые основания объективности и реалистичности этой оценки.

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

Отметим еще одно важное различие между экспериментальными и аналитическими оценками. Чтобы заниматься экспериментальными оценками - программу надо уже иметь, а аналитические могут помочь нам в решении вопроса – имеются ли достаточные основания заниматься реализацией тех или иных или даже всех других вариантов алгоритма решения задачи. Важная проблема, с которой мы сталкиваемся при эмпирическом анализе, — это определение природы входных данных и других факторов, оказывающих прямое влияние на производимые эксперименты. Обычно существуют три основных возможности: реальные данные, случайные данные и ошибочные данные. Реальные данные позволяют точно измерить параметры используемой программы; случайные данные гарантируют, что наши эксперименты тестируют алгоритм, а не данные; ошибочные данные гарантируют, что наши программы могут воспринимать любой направленный им ввод.

При анализе алгоритмов существуют две фундаментальные проблемы

1. Какими свойствами обладает данный алгоритм

2. Какие свойства должен иметь любой алгоритм, решающий данную задачу.

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

Вторая задача связана с изучением внутренних связей задачи, учет которых необходим при любой реализации (проблема нижних оценок)

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

⇐ Предыдущая 123 4 5 6 7 8 9 10 Следующая ⇒