Сложность вычислений: оценка эффективности алгоритмов
Цели и задачи
- Цель по SMART: к концу урока научиться определять асимптотическую сложность простых алгоритмов, сравнивать алгоритмы по числу операций и обосновывать выбор более эффективного решения.
- Сформировать представление о временной и пространственной сложности алгоритмов, обозначениях $O(1)$, $O(n)$, $O(n^2)$ и $O(\log n)$.
- Научиться выделять основную операцию алгоритма, оценивать количество её выполнений и записывать результат в асимптотической форме.
- Развивать умение анализировать программный код, работать с таблицами и цифровыми инструментами, аргументировать решение в паре и самостоятельно проверять выводы.
- Показать практическую значимость оценки сложности для разработки программ, обработки больших наборов данных и подготовки к дальнейшему обучению в области ИТ.
Планируемые результаты
Личностные
- Осознают связь эффективности алгоритма с качеством цифровых продуктов и будущей профессиональной деятельностью.
- Проявляют готовность проверять утверждения экспериментом и признавать необходимость уточнения собственного решения.
- Понимают ценность рационального использования вычислительных ресурсов.
- Проявляют ответственное отношение к совместной работе и корректному обсуждению разных способов решения.
Метапредметные
- Выделяют существенную информацию в описании алгоритма и представляют результаты анализа в таблице.
- Сравнивают теоретическую оценку сложности с результатами компьютерного эксперимента.
- Планируют последовательность анализа кода, формулируют гипотезу и проверяют её.
- Аргументированно представляют выводы, используют математические обозначения и цифровые инструменты.
Предметные
- Знают назначение оценки сложности алгоритмов и различия между временной и пространственной сложностью.
- Умеют определять порядок роста числа операций для последовательных действий, циклов и вложенных циклов.
- Умеют распознавать оценки $O(1)$, $O(\log n)$, $O(n)$ и $O(n^2)$ в простых алгоритмах.
- Владеют способом сравнения алгоритмов при увеличении размера входных данных.
- Умеют объяснить, почему асимптотическая оценка не равна точному времени выполнения программы.
Универсальные учебные действия (УУД)
Личностные УУД
- Определяют личный интерес к задачам алгоритмизации и направлениям применения информатики.
- Формируют смысл учебной деятельности через анализ реальных ограничений вычислительных систем.
- Оценивают собственную готовность применять теоретическую модель к практическому коду.
- Соблюдают нормы сотрудничества и уважительно относятся к обоснованным альтернативным решениям.
Регулятивные УУД
- Принимают учебную цель и формулируют критерии успешного анализа алгоритма.
- Планируют действия: определить входной размер, найти основную операцию, посчитать повторения, записать оценку.
- Сверяют собственный результат с эталоном и находят причину расхождения.
- Корректируют вывод после сопоставления теоретической оценки с экспериментальными данными.
Познавательные УУД
- Анализируют структуру циклов и устанавливают зависимость числа операций от $n$.
- Сравнивают функции роста и классифицируют алгоритмы по сложности.
- Строят простую модель времени выполнения алгоритма.
- Извлекают данные из таблицы или графика и формулируют вывод на их основе.
Коммуникативные УУД
- Распределяют роли в паре: аналитик, проверяющий и докладчик.
- Формулируют вопрос к решению другой пары и приводят аргументированный ответ.
- Используют математические и информатические термины в устном объяснении.
- Согласуют общий вывод при наличии разных оценок сложности.
Подготовка учителя к уроку
- Подготовить презентацию или интерактивную доску с графиками роста функций $1$, $\log n$, $n$, $n^2$ и таблицей кратких обозначений сложности.
- Создать в среде программирования или онлайн-интерпретаторе три короткие программы: поиск элемента, один цикл и вложенные циклы.
- Распечатать карточки трёх уровней сложности — по одной на каждого ученика и дополнительный комплект для пар.
- Подготовить лист анализа алгоритма с полями: размер входа, основная операция, число повторений, оценка, обоснование.
- Подготовить таблицу для компьютерного эксперимента с размерами входа 100, 1000, 5000 и 10000.
- Вывести на доску памятку: последовательные блоки оцениваются по максимальному порядку, вложенные циклы перемножают число повторений.
- Подготовить ноутбук учителя, проектор, доступ к среде исполнения программ и таймер.
- Подготовить стикеры трёх цветов для рефлексии и электронную форму или общий файл для фиксации результатов групп.
- Заранее проверить работу программ и отсутствие необходимости устанавливать дополнительное программное обеспечение.
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: включить учащихся в исследование практической проблемы эффективности алгоритмов.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и показывает на экране два способа поиска записи в списке из нескольких миллионов элементов: последовательный просмотр и деление области поиска пополам. «Представьте, что от скорости этого поиска зависит работа сервиса. Какой алгоритм вы выберете и почему?» | Индивидуально формулируют предположение; отвечают: «Нужно выбрать алгоритм, который выполняет меньше операций при большом размере данных». |
2 мин | Учитель объявляет приём «Проблемный вопрос»: «Можно ли заранее, ещё до запуска программы, оценить, как будет расти число операций? Сегодня мы не просто вспомним циклы, а научимся измерять эффективность алгоритма». | Обсуждают вопрос в парах 30 секунд, затем называют критерии: количество повторений, размер входных данных, память. |
Завершение этапа: учитель подводит итог: «Мы выяснили, что важна не только правильность результата, но и цена его получения. Сейчас проверим, какие знания о циклах помогут эту цену оценить».
Этап 2. Актуализация знаний (6 мин)
Цель этапа: восстановить способы подсчёта операций в последовательных и циклических алгоритмах.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель выводит код: «for i in range(n): print(i)». «Сколько раз выполнится команда вывода, если $n=10$, $n=1000$ и произвольное $n$? Какая величина здесь изменяется?» | Записывают ответы: «10, 1000 и $n$ раз»; называют размер входа $n$. |
2 мин | Учитель показывает код с двумя последовательными циклами по $n$ повторений и спрашивает: «Станет ли порядок роста квадратичным? Почему?» | Обсуждают в парах и формулируют: «Всего примерно $2n$ операций, поэтому порядок роста линейный». |
2 мин | Учитель показывает вложенные циклы: «for i in range(n): for j in range(n): операция». «Как получить число выполнений внутренней операции?» | Считают $n\cdot n=n^2$ и записывают предварительный вывод. |
Завершение этапа: учитель подводит итог: «Мы умеем считать повторения, но пока записываем точные выражения. Следующий шаг — договориться, какие части выражения существенны при больших $n$».
Этап 3. Постановка проблемы и целеполагание (4 мин)
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Цель этапа: сформулировать учебную задачу и критерии успешного анализа.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель записывает на доске выражения $3n+5$, $n^2+2n+1$ и $7$. «При больших объёмах данных какие слагаемые определяют рост? Почему точное число секунд не является универсальной характеристикой алгоритма?» | Сравнивают выражения и отвечают: «Главным является старший порядок: $n$, $n^2$ или постоянная величина; время зависит от компьютера и реализации». |
2 мин | Учитель предлагает сформулировать цель: «Закончите фразу: к концу урока я смогу…» и фиксирует на доске критерии: определить размер входа, найти основную операцию, оценить рост, обосновать выбор. | Формулируют цель: «Смогу определить сложность простого алгоритма и объяснить, какой из двух алгоритмов эффективнее». |
Завершение этапа: учитель подводит итог: «Цель определена. Теперь построим рабочую модель и сразу применим её к программам, а не будем ограничиваться запоминанием обозначений».
Этап 4. Открытие нового знания и ИКТ-исследование (10 мин)
Цель этапа: открыть способ определения асимптотической сложности и проверить его компьютерным экспериментом.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Учитель демонстрирует памятку: «$O(1)$ — постоянное число действий; $O(n)$ — один проход по данным; $O(n^2)$ — два вложенных прохода; $O(\log n)$ — уменьшение области поиска в несколько раз. При больших $n$ оставляем наиболее быстро растущий компонент». Затем разбирает: «В алгоритме есть $4n+3$ действий. Какова его сложность?» | Записывают определения и отвечают: «$O(n)$, потому что постоянные множители и слагаемые не меняют порядок роста». |
3 мин | Учитель открывает заранее подготовленный файл и говорит: «Запустите два фрагмента: один выполняет $n$ действий, другой — $n^2$ действий. Внесите в таблицу время для четырёх значений $n$. Не сравнивайте абсолютные секунды как универсальный закон — смотрите на изменение времени». | В парах запускают код, фиксируют измерения в таблице, строят предположение о росте времени. |
3 мин | Учитель задаёт вопросы: «Что произошло при увеличении $n$ в 10 раз? Почему второй алгоритм растёт значительно быстрее? Как эксперимент подтверждает теорию?» | Сравнивают строки таблицы и формулируют: «Линейный алгоритм растёт примерно в 10 раз, квадратичный — примерно в 100 раз; это согласуется с $O(n)$ и $O(n^2)$». |
Запись в тетрадях
- Асимптотическая сложность описывает порядок роста затрат алгоритма при увеличении размера входа.
- $O(1)$ — постоянная, $O(\log n)$ — логарифмическая, $O(n)$ — линейная, $O(n^2)$ — квадратичная сложность.
- Для оценки находят основную операцию и число её выполнений; постоянные множители и младшие слагаемые обычно отбрасывают.
Завершение этапа: учитель подводит итог: «Мы получили правило и проверили его на данных. Теперь каждая пара применит правило к отдельному фрагменту алгоритма и защитит свой вывод».
Этап 5. Первичное закрепление в парах (7 мин)
Цель этапа: отработать алгоритм анализа на программах с разной структурой циклов.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель раздаёт карточки и напоминает алгоритм «Четыре шага»: «Назовите $n$, выберите основную операцию, сосчитайте её повторения, запишите $O(...)$ и объясните». | Распределяют роли в паре и читают условие карточки. |
4 мин | Учитель предлагает задания: «А: обращение к элементу массива по индексу; Б: один цикл по $n$ элементам; В: два вложенных цикла; Г: бинарный поиск в отсортированном массиве. Запишите не только ответ, но и обоснование». Консультирует пары вопросами: «Что уменьшается на каждом шаге? Сколько раз запускается внутренний цикл?» | Решают карточку, заполняют лист анализа; ожидаемые ответы: «А — $O(1)$, Б — $O(n)$, В — $O(n^2)$, Г — $O(\log n)$». |
2 мин | Учитель организует краткую проверку: «Поднимите карточку с выбранной оценкой и объясните один спорный пункт». | Представляют решение, задают другой паре уточняющий вопрос и исправляют неточность при необходимости. |
Завершение этапа: учитель подводит итог: «Вы научились переходить от текста программы к порядку роста. Проверим теперь индивидуально, можете ли вы выполнить весь анализ без подсказки пары».
Этап 6. Самостоятельная практическая работа с самопроверкой (10 мин)
Цель этапа: диагностировать индивидуальное владение алгоритмом определения сложности.
Время | Действие учителя | Действие учеников |
|---|---|---|
6 мин | Учитель выдаёт индивидуальную работу. «Проанализируйте три фрагмента. В первом выполняется фиксированное число операций. Во втором цикл проходит по $n$ элементам. В третьем внешний и внутренний циклы выполняются по $n$ раз. Для каждого укажите основную операцию, число выполнений и сложность». Для сильных учащихся добавляет: «Объясните, почему алгоритм с $5n+20$ действий и алгоритм с $n$ действий имеют один порядок сложности». | Индивидуально заполняют три строки листа, записывают $O(1)$, $O(n)$, $O(n^2)$ и краткие обоснования. |
2 мин | Учитель показывает эталон на экране и просит выполнить самопроверку цветом: зелёный — верно, жёлтый — нужна коррекция, красный — требуется помощь. | Сверяют каждый пункт, подчёркивают место ошибки и записывают исправленный вариант. |
2 мин | Учитель разбирает типичную ошибку: «Два последовательных цикла по $n$ дают $O(n)$, а не $O(n^2)$. Квадратичный рост появляется при вложенности, когда одна операция повторяется внутри другой». | Фиксируют правило и объясняют его соседу одним предложением. |
Эталон решения
Для цикла, выполняющего одну операцию $n$ раз: число выполнений равно $n$, поэтому сложность $O(n)$. Для двух вложенных циклов: внешний цикл выполняется $n$ раз, а внутренний — по $n$ раз на каждой итерации, итого $n\cdot n=n^2$, поэтому сложность $O(n^2)$. Для фиксированного числа действий число операций не зависит от $n$, поэтому сложность $O(1)$. Выражение $5n+20$ имеет линейный порядок роста, так как при больших $n$ главным является слагаемое $n$.
Завершение этапа: учитель подводит итог: «Индивидуальная проверка показала, какой шаг уже стал уверенным, а какой требует внимания. В завершение свяжем результат с выбором алгоритма и зафиксируем личный вывод».
Этап 7. Рефлексия и домашнее задание (5 мин)
Цель этапа: осмыслить способ действия, выявить затруднения и определить дальнейшую практику.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель проводит рефлексию «Светофор»: «Поднимите зелёную карточку, если можете самостоятельно определить $O(1)$, $O(n)$ и $O(n^2)$; жёлтую — если нужна ещё одна тренировка; красную — если пока трудно». Затем просит написать на стикере одно правило и один вопрос. | Показывают карточку, записывают: «Сначала ищу основную операцию, затем считаю повторения»; формулируют личный вопрос. |
1 мин | Учитель предлагает «Билет на выход»: «Сравните алгоритмы с $100n$ и $n^2$ операций. При каком достаточно большом $n$ второй становится менее выгодным? Объясните без вычисления точного времени». | Записывают ответ: при $n>100$ квадратичный алгоритм выполняет больше операций, так как $n^2>100n$. |
2 мин | Учитель сообщает уровни домашней работы и напоминает: «Выберите обязательный уровень и, если готовы, добавьте повышающий или дополнительный. Важно не переписать ответ, а показать ход анализа». | Записывают задание, задают уточняющие вопросы и отмечают выбранный уровень. |
Завершение этапа: учитель подводит итог: «Сегодня вы научились оценивать алгоритм не по впечатлению, а по росту числа операций. На следующем уроке применим этот подход к поиску и сортировке данных и обсудим компромисс между временем и памятью».
Критерии оценивания практической работы
- «5» — верно определены сложности всех трёх фрагментов, указаны основные операции и приведено корректное обоснование через число повторений.
- «4» — правильно определены две сложности из трёх, в третьем допущена одна неточность, общий алгоритм анализа понятен.
- «3» — правильно определена хотя бы одна сложность и частично описан подсчёт операций; требуется помощь при различении последовательных и вложенных циклов.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Какой первый шаг вы выполняете при анализе алгоритма? | Проверка понимания общего алгоритма действия. |
Чем отличаются два последовательных цикла по $n$ и два вложенных цикла по $n$? | Выявление понимания различия между $O(n)$ и $O(n^2)$. |
Что показал компьютерный эксперимент о росте времени выполнения? | Связь теоретической модели с практическими данными. |
Какой вопрос по теме остался у вас? | Выявление индивидуальных затруднений и планирование следующей поддержки. |
Завершающее слово учителя
«Сегодня мы увидели, что эффективность алгоритма можно оценивать ещё до его запуска. Главная ошибка — путать два последовательных цикла с вложенными: в первом случае рост остаётся линейным, во втором появляется произведение $n\cdot n$. Вы уже умеете обосновывать выбор алгоритма с помощью обозначения $O(...)$, а не только угадывать ответ по коду. На следующем уроке мы применим этот инструмент к алгоритмам поиска и сортировки».
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Проанализировать 4 коротких фрагмента с постоянным действием, одним циклом, двумя последовательными циклами и двумя вложенными циклами; для каждого указать основную операцию, число выполнений и оценку сложности. | Закрепляет различение $O(1)$, $O(n)$ и $O(n^2)$; при проверке смотреть на обоснование, а не только на обозначение. |
Средний (повышающий) | Составить таблицу сравнения алгоритмов сложностью $O(1)$, $O(\log n)$, $O(n)$ и $O(n^2)$ для значений $n=10$, $100$ и $1000$, используя условное число операций. | Развивает умение сравнивать рост функций и интерпретировать данные; проверить корректность вычислений и вывод. |
Продвинутый (дополнительный) | Написать небольшую программу, которая измеряет время выполнения линейного и квадратичного фрагментов для трёх размеров входа, построить таблицу результатов и объяснить расхождение между теоретическим порядком и реальными секундами. | Формирует исследовательские навыки и понимание зависимости результата от оборудования, языка и реализации. |
Контрольные вопросы перед выходом: «Что обозначает параметр $n$? Как найти основную операцию? Почему $2n+7$ — это $O(n)$? В каком случае два цикла дают $O(n^2)$? Чем теоретическая сложность отличается от точного времени выполнения?»
