Урок 62
§36. Сложность вычислений
(§36. Сложность вычислений)
Содержание урока
Что такое сложность вычислений?
Что такое асимптотическая сложность?
Задачи
Задачи
1. Оцените количество операций для алгоритмов:
а) поиска всех делителей числа;
б) нахождения минимального и максимального элементов массива;
в) определения количества положительных элементов массива;
г) проверки числа на простоту.
В каждом случае опишите набор используемых элементарных операций. Определите асимптотическую сложность этих алгоритмов.
*2. Предложите алгоритм, позволяющий найти и вывести на экран те символы, которые встречаются в строке более одного раза. Оцените его асимптотическую сложность.
*3. Алфавит языка племени «тумба-юмба» содержит k символов. Предложите алгоритм построения всех возможных слов этого языка, имеющих длину п символов, и оцените его асимптотическую сложность.
Следующая страница 
§36. Сложность вычислений
Cкачать материалы урока
