Анализ алгоритмов: оценка эффективности и поиск узких мест
Цели и задачи
- Цель по SMART: к концу урока научиться анализировать простые алгоритмы, определять их временную сложность по числу выполнений основных операций и обосновывать, какой из двух алгоритмов эффективнее.
- Сформировать представление о сложности алгоритма как характеристике зависимости количества операций от размера входных данных.
- Научиться выделять основную операцию алгоритма, подсчитывать число её выполнений для последовательных, условных и циклических конструкций.
- Развивать умение сравнивать алгоритмы, объяснять результаты анализа и находить узкие места в программном решении.
- Воспитывать ответственное отношение к качеству программного продукта, самостоятельность при исследовании и готовность аргументированно защищать собственное решение.
Планируемые результаты
Личностные
- Осознавать связь эффективности алгоритмов с качеством цифровых продуктов и будущей профессиональной деятельностью.
- Проявлять познавательную мотивацию при исследовании способов ускорения алгоритмов.
- Понимать ценность точного, проверяемого и аргументированного объяснения результата.
- Проявлять самостоятельность при выборе способа анализа и оценке собственной работы.
Метапредметные
- Выделять существенную информацию в тексте алгоритма и представлять её в виде таблицы или математической зависимости.
- Планировать исследование, фиксировать промежуточные результаты и проверять гипотезы на небольших входных данных.
- Сравнивать несколько способов решения одной задачи по заданному критерию.
- Аргументированно формулировать выводы в устной и письменной форме, сотрудничать при решении исследовательской задачи.
Предметные
- Знать понятия «основная операция», «размер входных данных», «временная сложность» и обозначение порядка роста $O(...)$.
- Уметь определять порядок роста для последовательных действий и простых циклов.
- Уметь различать линейную, квадратичную и логарифмическую зависимости на качественном уровне.
- Уметь сравнивать два алгоритма при малых и больших значениях размера входных данных.
- Владеть способом пошагового анализа алгоритма и объяснения полученного результата.
Универсальные учебные действия (УУД)
Личностные УУД
- Определяют личный учебный дефицит при анализе алгоритмов и выбирают способ его устранения.
- Осознают практическую значимость оптимизации алгоритмов для программирования, анализа данных и разработки цифровых сервисов.
- Проявляют готовность принимать самостоятельное решение и отвечать за его обоснование.
- Оценивают собственный вклад в групповое исследование.
Регулятивные УУД
- Формулируют цель исследования алгоритма и планируют последовательность анализа.
- Выбирают основную операцию и устанавливают критерий сравнения решений.
- Осуществляют самоконтроль по чек-листу: определён вход, выбрана операция, подсчитаны повторы, сформулирован вывод.
- Обнаруживают ошибку в подсчёте и корректируют решение после проверки на примере.
- Оценивают результат по критериям точности, полноты и аргументированности.
Познавательные УУД
- Выделяют основную операцию и размер входных данных в описании алгоритма.
- Строят зависимость числа операций от размера входа и распознают характер её роста.
- Сравнивают последовательный и вложенный циклы по числу повторений.
- Используют таблицу значений и простой график как модели поведения алгоритма.
- Формулируют обобщение о влиянии структуры цикла на сложность.
Коммуникативные УУД
- Распределяют роли в группе: аналитик, проверяющий, оформитель и докладчик.
- Задают уточняющие вопросы о выбранной основной операции и способе подсчёта.
- Аргументируют вывод ссылкой на число повторений, а не только на интуитивную оценку.
- Сопоставляют разные решения и корректно предлагают исправления.
- Кратко представляют результат исследования классу.
Подготовка учителя к уроку
- Подготовить презентацию с проблемным вопросом, двумя фрагментами псевдокода, таблицей значений $n$, $n^2$, $\log_2 n$ и схемой алгоритма анализа.
- Распечатать карточки трёх уровней по одной на каждого ученика: базовые последовательные и линейные циклы, повышенные вложенные циклы, исследовательские задания на сравнение алгоритмов.
- Распечатать групповую карточку с алгоритмом анализа: определить вход, выбрать основную операцию, посчитать повторы, записать зависимость, обозначить порядок роста, сделать вывод.
- Подготовить лист самооценки на каждого ученика и мини-лист «Билет на выход» на каждого ученика.
- Вывести на доску памятку: «последовательные блоки складываются; повторение в цикле умножается; вложенные циклы перемножаются».
- Подготовить маркеры, стикеры двух цветов и четыре листа формата А3 для групповой работы.
- Подготовить ноутбук и проектор; при наличии компьютеров открыть среду для выполнения коротких фрагментов псевдокода или Python.
- Разделить класс на смешанные группы по 4 человека и заранее определить рабочие места групп.
- Подготовить таймер на 2, 5 и 7 минут для исследовательских этапов.
Ход урока
Этап 1. Организационный момент и мотивационный крючок (3 мин)
Цель этапа: включить учащихся в исследовательскую деятельность и показать практическую значимость анализа алгоритмов.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и показывает на экране два сообщения: «Алгоритм А обрабатывает 1 000 записей за секунду» и «Алгоритм Б обрабатывает 1 000 000 записей за секунду». «Представьте, что оба алгоритма дают правильный ответ. Почему разница в скорости может стать критичной для поисковой системы, банка или сервиса рекомендаций? Сегодня мы будем не просто запускать алгоритмы, а исследовать их поведение при росте объёма данных». | Фиксируют в тетради тему, приводят примеры: «пользователь ждёт ответа», «растёт число записей», «сервер тратит больше ресурсов». Формулируют предположение: «важно знать, как меняется число операций». |
2 мин | Учитель объявляет приём «Проблемный вопрос»: «Как по виду алгоритма заранее понять, будет ли он работать приемлемо на больших данных, даже если мы ещё не запускали программу на реальном сервере? Запишите индивидуальную гипотезу, затем обсудите её с соседом». | За 30 секунд записывают гипотезу, одну минуту обсуждают её в парах и предлагают варианты: «посчитать операции», «посмотреть на циклы», «сравнить время работы». |
Завершение этапа: учитель подводит итог: "Мы увидели, что правильность алгоритма ещё не гарантирует его практическую пригодность. Сейчас вспомним, какие конструкции программы влияют на число выполняемых действий, и подготовим инструменты для анализа."
Этап 2. Актуализация знаний и фиксация затруднения (6 мин)
Цель этапа: актуализировать знания о переменных, циклах и структуре алгоритма, выявить затруднение в оценке количества операций.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель демонстрирует псевдокод: «Для $i$ от 1 до $n$ выполнить: вывести $i$». «Сколько раз сработает команда вывода при $n=5$, $n=100$ и $n=1000$? Что здесь можно считать основной операцией?» | Записывают значения в таблицу: 5, 100 и 1000. Отвечают: «основная операция — вывод или действие внутри цикла». |
2 мин | Учитель показывает второй фрагмент: «Для $i$ от 1 до $n$ выполнить: для $j$ от 1 до $n$ выполнить: сравнить $i$ и $j$». «Попробуйте без полного выполнения программы определить число сравнений при $n=3$ и $n=10». | Сначала считают для $n=3$: 9 сравнений, затем для $n=10$: 100. Обсуждают, что вложенный цикл даёт $n\cdot n$ повторений. |
2 мин | Учитель организует «Светофор»: «Зелёная карточка — можете объяснить, почему получились такие числа; жёлтая — понимаете пример, но затрудняетесь обобщить; красная — пока не видите способ анализа». После сигналов уточняет: «Что именно вызывает трудность: выбор операции, подсчёт повторений или запись общего результата?» | Поднимают карточки, называют затруднение. Формулируют: «нужно научиться переходить от конкретных значений к зависимости от $n$». |
Завершение этапа: учитель подводит итог: "Мы умеем считать отдельные примеры, но нам нужен общий способ описать поведение алгоритма при любом размере входа. Сформулируем цель и порядок исследования."
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: сформулировать учебную задачу и критерии успешного анализа алгоритма.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель проводит «Сократовский диалог»: «Если вход содержит $n$ элементов, что должно измениться при переходе от $n=10$ к $n=1000$? Достаточно ли сообщить одно время запуска? Почему два алгоритма могут различаться при больших $n$, хотя на маленьких данных работают почти одинаково?» | Отвечают: «увеличится число операций», «одного измерения недостаточно», «важен характер роста». Формулируют понятие размера входных данных как числа элементов или другого параметра, определяющего объём работы. |
2 мин | Учитель фиксирует на доске план: «1. Найти размер входа. 2. Выбрать основную операцию. 3. Посчитать число её выполнений. 4. Описать зависимость от $n$. 5. Сравнить алгоритмы и сделать вывод». «Какой результат покажет, что цель достигнута?» | Записывают план, предлагают критерии: «выделена операция», «получена формула или порядок роста», «вывод подтверждён расчётом». |
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Запись в тетрадях
Тема урока. Анализ алгоритма — определение количества основных операций и характера его роста при увеличении размера входных данных. План анализа: размер входа → основная операция → число повторений → зависимость → порядок роста → вывод.
Завершение этапа: учитель подводит итог: "У нас появился общий алгоритм самого анализа. Теперь проверим его на простых конструкциях и увидим, как структура программы превращается в математическую зависимость."
Этап 4. Открытие нового знания: порядок роста (10 мин)
Цель этапа: вывести правила анализа последовательных действий, одиночного и вложенного циклов и ввести обозначение $O(...)$.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель показывает на экране псевдокод: «прочитать $n$ чисел; для каждого числа выполнить одно сравнение; вывести результат». «Выберем сравнением основную операцию. Сколько раз она выполнится? Как изменится число сравнений при удвоении $n$?» | Определяют $n$ сравнений, записывают зависимость $T(n)=n$. Формулируют: «при удвоении входа число операций примерно удваивается». |
3 мин | Учитель записывает рядом два последовательных фрагмента: «один цикл на $n$ повторений» и «два последовательных цикла на $n$ повторений». «Получаем $n+n=2n$. Для оценки порядка роста постоянный множитель не меняет тип зависимости, поэтому оба случая относят к $O(n)$.» | Сверяют рассуждение, записывают: $n+n=2n$, порядок роста $O(n)$. Объясняют, что последовательные участки анализируются сложением. |
2 мин | Учитель возвращается к вложенному циклу: «Для $i$ от 1 до $n$, для $j$ от 1 до $n$ выполнить сравнение». «Внешний цикл запускает внутренний $n$ раз, а внутренний каждый раз выполняется $n$ раз. Значит, всего $n\cdot n=n^2$, порядок роста $O(n^2)$.» | Строят короткую схему из $n$ строк по $n$ действий, записывают $T(n)=n^2$ и $O(n^2)$. Отвечают: «при удвоении $n$ число операций возрастает примерно в четыре раза». |
2 мин | Учитель показывает фрагмент: «пока $n>1$: заменить $n$ на $n/2$». «После каждого шага размер уменьшается в два раза. Сколько шагов потребуется, чтобы дойти до единицы? Это логарифмическая зависимость: $O(\log n)$. На уроке нам важно распознавать её по последовательному делению размера задачи.» | Записывают признак логарифмического роста: размер задачи на каждом шаге уменьшается в постоянное число раз. Сравнивают три типа: $O(\log n)$, $O(n)$, $O(n^2)$. |
Запись в тетрадях
- Последовательные участки: число операций складывается; при оценке порядка роста выбирают наиболее быстро растущий член.
- Один цикл с $n$ повторениями обычно даёт $O(n)$.
- Два вложенных цикла по $n$ повторений обычно дают $O(n^2)$.
- Последовательное уменьшение размера задачи в несколько раз обычно даёт $O(\log n)$.
- Чем медленнее растёт функция сложности, тем лучше алгоритм масштабируется при больших входных данных.
Завершение этапа: учитель подводит итог: "Мы получили не набор отдельных формул, а язык для сравнения алгоритмов. Теперь применим его в группах: каждой группе предстоит доказать свой вывод подсчётом операций и объяснить его классу."
Этап 5. Исследовательская работа в группах (9 мин)
Цель этапа: применить алгоритм анализа к фрагментам разной структуры и сформулировать аргументированный вывод.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель распределяет роли и раздаёт карточки: «В каждой группе есть аналитик, проверяющий, оформитель и докладчик. На листе А3 запишите размер входа, основную операцию, число повторений, порядок роста и вывод. Не ограничивайтесь ответом $O(n)$ или $O(n^2)$ — объясните, откуда он получен». | Распределяют роли, читают условие карточки и фиксируют порядок действий. |
5 мин | Учитель предлагает задания. Группа 1 анализирует один цикл по $n$ элементов. Группа 2 анализирует два последовательных цикла по $n$ элементов. Группа 3 анализирует два вложенных цикла: внешний — от 1 до $n$, внутренний — от 1 до $n$. Группа 4 анализирует цикл, в котором на каждом шаге $n$ заменяется на $n/2$. Учитель перемещается между группами и задаёт вопросы: «Что именно вы считаете основной операцией? Сколько раз выполняется внутренний цикл при каждом значении внешнего? Как проверить ваш вывод на $n=4$?» | В группах считают операции, заполняют лист А3, проверяют результат на $n=4$ или $n=8$, отмечают возможную ошибку стикером и исправляют её. Получают соответственно $O(n)$, $O(n)$, $O(n^2)$ и $O(\log n)$. |
3 мин | Учитель проводит краткую защиту: «Докладчику каждой группы — одна минута. Назовите алгоритм, основную операцию, подсчёт и практический вывод. Остальные группы задают по одному уточняющему вопросу». | Докладчики представляют решения. Одноклассники задают вопросы: «Почему два последовательных цикла не дают $O(n^2)$?», «Почему вложенность приводит к умножению?», «Как проверили логарифмический случай?» |
Завершение этапа: учитель подводит итог: "Группы показали, что одинаковый внешний размер входа может приводить к разному росту затрат. Теперь каждый индивидуально проверит, умеет ли он применять этот способ без поддержки группы."
Этап 6. Первичное закрепление и самостоятельная работа с самопроверкой (8 мин)
Цель этапа: закрепить умение определять порядок роста и выявлять ошибочные рассуждения.
Время | Действие учителя | Действие учеников |
|---|---|---|
5 мин | Учитель раздаёт индивидуальные карточки трёх уровней. «Базовый уровень: определите порядок роста для одного цикла по $n$ элементам и последовательности из трёх таких циклов. Повышенный уровень: определите порядок роста вложенных циклов, где внутренний цикл выполняется от 1 до $i$. Продвинутый уровень: сравните алгоритмы $A$ с $T_A(n)=3n+5$ и $B$ с $T_B(n)=n^2$. Обоснуйте, какой выгоднее при больших $n$. Запишите не только ответ, но и два шага рассуждения». | Индивидуально решают выбранный уровень. Для вложенного случая получают сумму $1+2+...+n=\frac{n(n+1)}{2}$ и делают вывод $O(n^2)$. Для сравнения объясняют, что при больших $n$ линейный алгоритм растёт медленнее квадратичного. |
3 мин | Учитель выводит эталон на экран и проводит «Самопроверку по чек-листу»: «Поставьте плюс, если указали размер входа, выделили основную операцию, обосновали число повторений, записали порядок роста и сформулировали вывод. Если есть ошибка, подчеркните место, а рядом запишите исправление». | Сверяют решение с эталоном, отмечают пункты чек-листа, исправляют одну обнаруженную ошибку. Показывают светофор: зелёный — могу объяснить, жёлтый — нужна ещё тренировка, красный — нужна помощь. |
Эталон решения
Для вложенных циклов, где внешний индекс $i$ принимает значения от 1 до $n$, а внутренний выполняется $i$ раз, общее число операций равно $T(n)=1+2+...+n=\frac{n(n+1)}{2}$. Раскрываем выражение: $T(n)=\frac{n^2+n}{2}$. При больших $n$ главным является член $n^2$, поэтому порядок роста — $O(n^2)$. Для сравнения $T_A(n)=3n+5$ имеет линейный рост $O(n)$, а $T_B(n)=n^2$ — квадратичный рост $O(n^2)$; при достаточно больших $n$ алгоритм A эффективнее, несмотря на постоянный множитель 3.
Завершение этапа: учитель подводит итог: "Самостоятельная проверка показала, что важен не только итоговый символ $O(...)$, но и путь к нему. На заключительном этапе применим этот способ к ситуации, близкой к реальной разработке, и оценим собственное понимание."
Этап 7. Включение в систему знаний и рефлексия (5 мин)
Цель этапа: связать анализ сложности с выбором алгоритма в практической ситуации и осмыслить результат урока.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель предлагает кейс: «Сервис должен обработать список из 10 000 записей. Алгоритм A выполняет примерно $5n$ операций, алгоритм B — $n^2$ операций. Какой вариант вы предложите команде разработчиков? Можно ли выбрать B только потому, что его код короче? Обоснуйте ответ по формуле и характеру роста». | В парах вычисляют порядок величин: для A около 50 000 операций, для B около 100 000 000. Формулируют: «выбираем A, потому что линейный рост существенно лучше квадратичного на больших данных». Объясняют, что краткость кода не равна эффективности. |
2 мин | Учитель организует «Одноминутку»: «Закончите три фразы: сегодня я научился; теперь я могу; мне ещё нужно потренироваться в…». Затем просит двух учеников озвучить разные варианты. | Заполняют три фразы, называют собственный результат и трудность: «выбор основной операции», «анализ вложенных циклов», «сравнение роста функций». |
Завершение этапа: учитель подводит итог: "Сегодня вы научились смотреть на алгоритм как на объект исследования: выделять операцию, считать повторы и предсказывать поведение на больших данных. Осталось зафиксировать результат и выбрать уровень домашней практики."
Этап 8. Итог урока и домашнее задание (0 мин)
Цель этапа: оформить итог урока и дать дифференцированное задание для закрепления.
Время | Действие учителя | Действие учеников |
|---|---|---|
0 мин | Учитель заранее объявляет домашнее задание после рефлексии: «Выберите обязательный уровень или добавьте повышенный и продвинутый. Перед сдачей проверьте каждое решение по пяти шагам анализа». | Записывают выбранный уровень и критерии проверки в дневник. |
Критерии оценивания практической работы
- «5» — верно выполнены все пункты выбранной карточки, указаны размер входа и основная операция, корректно подсчитано число повторений, порядок роста обоснован, вывод сформулирован точно.
- «4» — решение в основном верное, но допущена одна неточность в записи формулы, обозначении порядка роста или объяснении; ход рассуждения понятен.
- «3» — определены размер входа и хотя бы одна существенная часть подсчёта, но есть ошибки в анализе вложенности или отсутствует развёрнутое обоснование.
- Ниже базового уровня — не выделена основная операция или вывод не связан с числом повторений; работа требует повторного анализа по памятке.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Какой шаг анализа алгоритма теперь выполняется у вас уверенно? | Выявление освоенного действия и осознание личного результата. |
Почему два последовательных цикла по $n$ элементов обычно относят к $O(n)$, а два вложенных — к $O(n^2)$? | Проверка понимания различия между сложением и умножением числа повторений. |
Какую ошибку вы обнаружили при самопроверке и как её исправили? | Диагностика регулятивных действий: контроль и коррекция. |
Какой вопрос по анализу алгоритмов вы хотели бы исследовать дальше? | Поддержка познавательной инициативы и связь с дальнейшим изучением алгоритмов. |
Завершающее слово учителя
"Сегодня мы увидели, что анализ алгоритма позволяет заранее оценить его поведение на больших объёмах данных. Главная ошибка — называть сложность только по внешнему виду кода, не выделив основную операцию и не посчитав повторения. Используйте пятишаговый алгоритм анализа при решении задач и чтении программ. На следующем уроке мы продолжим сравнивать алгоритмы и рассмотрим, как выбирать эффективный способ решения конкретной задачи."
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Проанализировать 4 простых фрагмента псевдокода: один последовательный блок, один цикл по $n$ элементам, два последовательных цикла и два вложенных цикла. Для каждого указать размер входа, основную операцию, число повторений и порядок роста. | Закрепляет базовый алгоритм анализа; при проверке смотреть на различие между сложением и умножением повторений. |
Средний (повышающий) | Решить 3 задания на сравнение алгоритмов: определить порядок роста для цикла с внутренним числом повторений $i$, цикла с делением размера входа пополам и пары функций $4n+7$ и $n^2$. Для каждого написать краткое обоснование. | Развивает умение переходить от псевдокода к формуле и сравнивать алгоритмы при больших значениях входа. |
Продвинутый (дополнительный) | Исследовать два способа поиска элемента в упорядоченном списке: последовательный просмотр и деление диапазона пополам. Составить таблицу числа шагов для нескольких значений $n$, определить порядок роста и написать вывод о применимости методов. | Формирует исследовательское мышление и связывает линейную и логарифмическую сложность с практической задачей поиска. |
Контрольные вопросы перед выходом из класса: «Что называют размером входных данных? Как выбрать основную операцию? Почему вложенные циклы часто дают произведение числа повторений? Какой порядок роста медленнее: $O(n)$ или $O(n^2)$? Назовите два шага, которые вы выполните перед тем, как сравнивать алгоритмы».