Понятие анализа алгоритма

Размещено на http://www.allbest.ru/

Лекция

на тему: "Понятие анализа алгоритма"

План

1. Основные характеристики алгоритма при его анализе. Вычислительная сложность алгоритма

2. Классы входных данных

3. Сложность алгоритма по памяти

4. Оценка вычислительной сложности алгоритма

1. Основные характеристики алгоритма при его анализе. Вычислительная сложность алгоритма

Одну и ту же задачу может решать множество алгоритмов. Эффективность работы каждого из них описывается разнообразными характеристиками. Основные характеристики - это:

· вычислительная сложность;

· запросы к памяти.

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

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

а) нас интересует относительная эффективность алгоритма;

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

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

Два самых больших класса алгоритмов - это:

· алгоритмы с повторением,

· рекурсивные.

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

Рекурсивные алгоритмы разбивают большую задачу на фрагменты и применяются к каждому фрагменту отдельно. Такие алгоритмы называются иногда "разделяй и властвуй". В процессе решения большой задачи путем деления ее на меньшие создаются небольшие простые и понятные алгоритмы. Анализ рекурсивного алгоритма требует подсчета количества операций, необходимых для разбиения задачи на части, выполнения алгоритма на каждой из частей и объединения отдельных результатов для решения задачи в целом. Объединяя эту информацию и информацию о числе частей, мы можем вывести рекурентное соотношение для сложности алгоритма.

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

Одну и ту же задачу часто можно решить при помощи различных алгоритмов. Анализ алгоритмов дает инструмент для выбора алгоритма.

Пример. Выбрать наибольшую из трех величин .

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

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

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

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

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

2. Классы входных данных

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

Если список изначально упорядочен в порядке убывания, то перед началом цикла будет сделано одно присваивание, а в теле цикла присваиваний не будет вообще. Если список первоначально упорядочен по возрастанию, то всего будет сделано присваиваний. При анализе необходимо рассмотреть различные возможные множества входных данных, поскольку при ограничении одним множеством, оно может оказаться тем самым, на котором решение самое быстрое (медленное). В результате можно получить ложное представление об алгоритме. Вместо этого, как правило, рассматриваются все типы входных множеств. Для этого различные входные множества разбиваются на классы в зависимости от поведения алгоритма на каждом множестве. Такое разбиение позволяет уменьшить количество рассматриваемых возможностей. Например, число различных расстановок 10 различных чисел в списке есть 10!=3628800. Применим к списку из 10 чисел алгоритм поиска наибольшего элемента. Имеется 362880 входных множеств, у которых первое число является наибольшим; они все помещаются в один класс. Для любого множества из этого класса алгоритм сделает единственное присваивание. Если наибольшее по величине число стоит на втором месте, то алгоритм сделает ровно два присваивания. Все такие множества (их 362880) можно поместить в другой класс. Очевидно, число присваиваний будет на единицу возрастать при последовательном изменении положения наибольшего числа от 1 до . Таким образом можно разбить все входные множества на разных классов по числу производимых присваиваний. Очевидно, нет необходимости выписывать или описывать детально все множества, оказавшиеся в одном классе.

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

3. Сложность алгоритма по памяти

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

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

Спрос на компьютерную память велик, поэтому и важен вопрос, какие данные необходимо хранить, а также эффективные способы хранения. Проиллюстрируем сказанное на примере. Предположим, что производится запись вещественного числа из сегмента [-10,10], имеющего один десятичный знак после запятой. При записи вещественного числа большинство компьютеров потратит от 4 до 8 байтов памяти. Однако если предварительно умножить число на 10, то для хранения полученного целого числа из сегмента [-100,100] потребуется всего 1 байт.

При взгляде на программное обеспечение, предлагаемое на рынке сегодня, ясно, что необходимый подробный анализ памяти во многих случаях проведен не был. Объем памяти, необходимый даже для сравнительно простых программ, измеряется мегабайтами. Разработчики программ часто не отдают себе отчет в необходимости экономии места, полагая, что если у пользователя недостаточно памяти, то он может ее приобрести и установить дополнительно. Этот подход является крайне неправильным и негативным, в результате его компьютеры приходят "в негодность" задолго до того, как они действительно устаревают.

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

4. Оценка вычислительной сложности алгоритма

Подсчет вычислительной сложности алгоритма состоит из двух основных шагов:

Шаг 1. Выбор значимой операции или группы операций.

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

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

· сравнение,

· арифметические операции.

Арифметические операции разбиваются на две группы:

· аддитивные,

· мультипликативные.

Аддитивные операторы (сложения) включают сложение, вычитание, увеличение и уменьшение счетчика.

Мультипликативные операторы (умножения) включают умножение, деление, взятие остатка по модулю.

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

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

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

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

,

где - длина массива входных данных.

Если рассмотреть графики этих функций (рис. 1).

Рис. 1

Например, на промежутке от 1 до 35, то становится очевидным, что несмотря на то, что функция:

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

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

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

Таблица 1

Для иллюстрации последующего вывода рассмотрим пример функции, которая трактуется как закон зависимости количества арифметических операций некоторого гипотетического алгоритма от размера входных данных :

.

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

Определение. Говорят, что функции и связаны соотношением (или сравнимы):

(читается: функция есть О-большое от ), если

.

Рассмотрим другой пример:

.

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

,

Из чего вытекает, что

.

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

Приложение

Вопросы:

1. Какие основные характеристики алгоритма оцениваются при его анализе?

2. Как целесообразно оценивать "время" выполнения алгоритма? Почему? Что такое вычислительная сложность алгоритма?

3. В каких случаях сравнивается эффективность работы разных алгоритмов?

4. Должен ли анализ алгоритма учитывать особенности компьютера, на котором этот алгоритм реализован? Почему?

5. Влияют ли входные данные задачи на последовательность действий алгоритма? Привести пример.

6. Что представляют из себя классы входных данных?

7. Насколько значимым в настоящее время является вопрос используемой алгоритмом памяти?

8. Какие предварительные шаги предпринимаются для оценки вычислительной сложности алгоритма?

9. На какие две группы разбиваются арифметические операции? Почему?

10. Какие наборы данных желательно найти при оценке вычислительной сложности алгоритма?

11. Что называется скоростью роста алгоритма?

12. Что такое порядок вычислительной сложности алгоритма? Как он оценивается?

Размещено на Allbest.ru