Вопросы

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

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

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

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

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

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

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

_{Литература}

1. Дж. Макконнелл. Основы современных алгоритмов. 2-е дополненное издание. – М.: Техносфера, 2004. – 368 с.

2. Гуц А.К. Математическая логика и теория алгоритмов: Учебное пособие. – Омск: Изд-во Наследие. Диалог-Сибирь, 2003. – 108 с.

3. Деммель Дж. Вычислительная линейная алгебра / Дж.Деммель; пер.с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 430 с.

4. Бахвалов Н.С. Численные методы / Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков. — М.: БИНОМ. Лаборатория знаний, 2006. — 636 с.

5. Каханер Д. Численные методы и программное обеспечение / Д.Каханер, К.Моулер, С.Нэш; пер. с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 575 с.

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

1. Предварительные шаги для оценки вычислительной сложности алгоритма

2. Скорость роста алгоритма

3. Анализ подходов, связанных с поиском информации

1. Предварительные шаги для оценки вычислительной сложности алгоритма

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

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

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

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

• _{Сравнение,}

• _{Арифметические операции.}

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

• _{Аддитивные,}

• _{мультипликативные.}

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

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

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

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

2. Скорость роста алгоритма

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

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

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

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

_{Рис. 4.1.}

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

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

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

_{Таблица 4.1-}

1 2 5 10 15 20 30 40 50 60 70 80 90 100	0.0 1.0 2.3 3.3 3.9 4.3 4.9 5.3 5.6 5.9 6.1 6.3 6.5 6.6	1 4 25 100 225 400 900 1600 2500 3600 4900 6400 8100 10000	1 8 125 1000 3375 8000 27000 64000 125000 216000 343000 512000 729000 1000000	2 4 32 1024 32768 1048576 1073741824 1099511627776 1125899906842620 1152921504606850000 1180591620717410000000 1208925819614630000000000 12379400392853800000000000000 1267650600228230000000000000000

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

.

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

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

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

.

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

.

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

,

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

.

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