11 класс, углублённый уровень. Обзорный практикум к четырнадцатой паре: шесть задач — остановится ли программа, где ошибётся проверенная функция и как растёт время работы.
153, а не 153 раза.
На КЕГЭ ответ читает машина, и здесь так же.Задача алгоритмически неразрешима, если не существует алгоритма, который решает её при любых входных данных. Самая известная — задача останова (Тьюринг, 1936): по тексту любой программы и её входным данным узнать, завершится ли она.
Почему такой программы-«анализатора» нет. Допустим, она есть. Напишем программу Наоборот: она берёт текст программы, спрашивает анализатор, остановится ли эта программа на собственном тексте, и делает наоборот — если «остановится», уходит в вечный цикл, если «нет» — сразу останавливается. Что будет, если дать Наоборот её собственный текст? Остановится — значит, анализатор сказал «нет»; не остановится — значит, он сказал «да». Анализатор ошибся в любом случае — значит, его не бывает.
«Запустить и подождать» не помогает: если программа не остановилась за час, неизвестно, остановится ли она через два.
Не бывает и программы, которая про любую программу скажет, верно ли та работает на всех входах: с её помощью решалась бы задача останова. Тесты помогают, но тестирование показывает наличие ошибок, а не их отсутствие (Э. Дейкстра): тестов конечное число, входов — бесконечно много. Функция, верная на числах до 100, может ошибиться на 121.
Неразрешима задача для всех программ сразу. Про конкретную программу часто можно рассуждать. Если всё, что программа помнит, — одно число n, выпиши его значения столбиком: дошли до выхода из цикла — программа завершится; значение повторилось — дальше всё пойдёт по тому же кругу, программа не завершится никогда.
Время работы оценивают числом действий в зависимости от размера данных n, память — числом хранимых значений. Важен порядок роста: O(n²) — растёт не быстрее c·n².
| что в программе | сколько раз выполнится тело | порядок |
|---|---|---|
| цикл по n, в нём цикл по m | n · m | n² |
| внутренний цикл до i (или от i до n) | 0 + 1 + … + (n − 1) = n(n − 1)/2 | n² |
| три цикла, i < j < k | n(n − 1)(n − 2)/6 | n³ |
| i умножается на 2, пока i < n | столько, во сколько шагов 2c дорастёт до n | log n |
| цикл по n, в нём деление пополам | n · (число делений) | n · log n |
| сложность | n выросло в r раз |
|---|---|
| n | время ×r |
| n² | время ×r² (вдвое больше n — вчетверо дольше) |
| n³ | время ×r³ |
| 2ⁿ (перебор) | n выросло на d — время ×2d |
Таблица n × n чисел при n вдвое больше занимает вчетверо больше памяти. Паролей длины L из k знаков — kL: длиннее на один знак — перебор в k раз дольше.
Одну задачу решают алгоритмы разной сложности: поиск — линейный (n сравнений) и двоичный (около log₂n, только в упорядоченном массиве); сортировка — выбором (n(n − 1)/2) и слиянием (около n · log₂n). Сравнить a·n² и b·n просто: a·n² > b·n при n > b/a. Полиномиальные алгоритмы (n, n², n³) при больших n всегда выгоднее переборных (2ⁿ), хотя при малых n бывает наоборот: 2⁵ = 32 < 5³ = 125. В заданиях 26–27 ЕГЭ перебор всех пар для n = 10⁶ — это 10¹² действий, и программа не успеет: нужен алгоритм порядка n.
Материалы подготовлены с использованием технологий искусственного интеллекта.