Урок 34
§36. Сложность вычислений
(§36. Сложность вычислений)

Содержание урока

Что такое сложность вычислений?

Примеры

Что такое асимптотическая сложность?

Алгоритмы поиска

Алгоритмы сортировки

Вопросы и задания

Задачи

Задачи

1. Оцените количество операций для алгоритмов:

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

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

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

*3. Алфавит языка племени «тумба-юмба» содержит k символов. Предложите алгоритм построения всех возможных слов этого языка, имеющих длину п символов, и оцените его асимптотическую сложность.

Следующая страница §36. Сложность вычислений

Cкачать материалы урока