Сложность вычислений | Задачи (11 кл. 136 ч.)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углублённый курс, по 4 часа в неделю)


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



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

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

Примеры

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

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

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

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

Задачи


Задачи


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

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

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

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

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

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



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







Наверх