Упражнения. 1. С какой целью проводится оценка ресурсной эффективности алгоритмов?

Вопросы

Набор для практики

1. С какой целью проводится оценка ресурсной эффективности алгоритмов?

2. Почему в теории анализа алгоритмов нет привязки к конкретной реализации?

3. Могут ли оценки временной сложности для худшего и лучшего случаев совпадать? Подтвердите вывод примерами.

4. Охарактеризуйте область применения алгоритмов классов сложности πE и πF.

5. В чем особенность оценки трудоемкости рекурсивных алгоритмов?

6. Оцените временную трудоемкость рекурсивного и итерационного способов вычисления факториала целого неотрицательного числа. Определите класс сложности алгоритмов в каждом случае. Объясните результат.

1. Выполните анализ временной сложности алгоритмов простых сортировок. Проведите сравнительный анализ полученных результатов. Определите классы этих алгоритмов в зависимости от функции трудоемкости.

2. Выполните анализ временной трудоемкости алгоритма решения задачи о Ханойских башнях. Определите класс этого алгоритма в зависимости от функции трудоемкости.

3. Выполните анализ трудоемкости конструкций вложенных циклов для n =100, n =10⁶, n =10⁹. Составьте функцию временной трудоемкости алгоритма и определите его класс сложности. Считать, что все указанные операции корректны. Возможное переполнение разрядов не учитывать.

k=0;

for (a=0; a<n; a++)

for (b=0; b<n; b++)

for (c=0; c<n; c++)

k++;

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

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

Литература

1. Ахо А., Хопкрофт Дж., Ульман Д. Структуры данных и алгоритмы. Уч. пособие. — М.: Вильямс, 2000. – 384с.

2. Головешкин, В.В., Ульянов, М.В. Теория рекурсии для программистов /В.А.Головешкин, М.В. Ульянов. – М.: ФИЗМАТЛИТ, 2006. – 296 с.

3. Есаян, А. Р. Рекурсия в информатике: Учеб. пособие для студентов пед. вузов: Ч. 1: Корзина разнообразных задач. / А.Р. Есаян. – Тула: Изд-во ТГПУ им. Л. Н. Толстого, 2000. – 90 с.

4. Кормен Т., Леверсон Ч.., Ртвест Р. Алгоритмы. Построение и анализ. — М.: МЦНМО, 1999. – 960 с.

5. Подбельский, В.В. Язык Си++: учеб. пособие / В.В. Подбельский. – М.: Финансы и статистика, 2005. – 560 с.

6. Сэджвик Р. Фундаментальные алгоритмы на С++. Части 1-4. Анализ, структуры данных, сортировка, поиск. — М.: Диасофт, 2001. – 687 с.

7. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учебное пособие. - М.: Финансы и статистика, 2004. – 464 с.

Дата добавления: 2014-01-04