Теория алгоритмов

2020-2021 учебный год

Практические занятия

Практика 13
Решение задач на определение сложности алгоритма 

Пример 1

1. Изучите по учебнику алгоритм сортировки подсчетом. 
Запишите алгоритм на языке Си. 
Определите асимптотическую сложность алгоритма способом, 
приведенном в учебнике на с. 16
Поляков К.Ю., Еремин Е.А. Основы теории алгоритмов.

2. Изучите по учебнику рекомендации по определению 
практической временной сложности алгоритма. 
Запишите алгоритм на языке Си, 
с. 319-320.
Колдаев В. Д. Основы алгоритмизации и программирования: 
Учебное пособие / В.Д. Колдаев; Под ред. Л.Г. Гагариной. - 
Москва : ИД ФОРУМ: ИНФРА-М, 2015. - 416 с.
https://znanium.com/catalog/document?id=170583

3. Выполните по учебнику упражнение на сравнение временных 
сложностей алгоритмов сортировки.
Запишите алгоритмы на языке Си, 
с. 318-319.
Колдаев В. Д. Основы алгоритмизации и программирования: 
Учебное пособие / В.Д. Колдаев; Под ред. Л.Г. Гагариной. - 
Москва : ИД ФОРУМ: ИНФРА-М, 2015. - 416 с.
https://znanium.com/catalog/document?id=170583


4. Изучите по учебнику алгоритм бинарного поиска. 
Запишите алгоритм на языке Си. 
Определите асимптотическую сложность алгоритма способом, 
приведенном в учебнике на с. 62, с.235.
Колдаев В. Д. Основы алгоритмизации и программирования: 
Учебное пособие / В.Д. Колдаев; Под ред. Л.Г. Гагариной. - 
Москва : ИД ФОРУМ: ИНФРА-М, 2015. - 416 с.
https://znanium.com/catalog/document?id=170583

5. Подготовьте презентацию по теме 
«Определение сложности алгоритма».
по материалам учебника, изучив
методы анализа временной сложности алгоритма
и классификацию алгоритмов по временной сложности
с. 13-23
Канцедал С. А. Алгоритмизация и программирование : 
учеб. пособие / C.А. Канцедал. — Москва : ИД «ФОРУМ» : 
ИНФРА-М, 2018. — 352 с.
https://znanium.com/catalog/document?id=302077



Решение задач на определение сложности алгоритма. 
Анализ алгоритмов поиска. 
Анализ алгоритмов сортировки.