Конечность алгоритма
Конечность алгоритма означает, что выполнение алгоритма должно завершиться после конечного числа шагов. Исполнитель не может бесконечно повторять команды, если алгоритм предназначен для решения задачи.
Конечность — одно из свойств алгоритма. Число шагов заранее не обязано быть одинаковым для всех входных данных: для одних данных алгоритм может остановиться быстро, а для других — выполнить больше команд. Важно лишь, чтобы для каждого допустимого входа это число было конечным.
Здесь \(N\) — число выполненных шагов алгоритма. Условие конечности означает, что для каждого запуска существует такое конечное \(N\), после которого исполнитель останавливается. Если алгоритм содержит цикл, его условие выхода должно когда-нибудь выполниться или число повторений должно быть ограничено.
Алгоритм «пока число \(n\) больше нуля, вычитать из него 1» конечен для целого неотрицательного \(n\): после \(n\) шагов получится 0, и цикл завершится. Если же команда каждый раз увеличивает \(n\) на 1, условие \(n>0\) не исчезает, поэтому выполнение становится бесконечным.
Результативность алгоритма означает получение требуемого результата после выполнения команд, а конечность — сам факт остановки за конечное число шагов. Алгоритм может завершиться, но дать неправильный результат; такой алгоритм конечен, но неверен.
Конечность также отличается от определённости алгоритма. Определённость требует, чтобы на каждом шаге команда была однозначной и понятной исполнителю. Даже однозначные команды могут образовать бесконечный цикл, если среди свойств алгоритма не выполнено требование конечности.
Какой алгоритм нарушает требование конечности?
Главное
- Конечность требует остановки алгоритма за конечное число шагов для каждого допустимого входа.
- Число шагов может зависеть от входных данных, но не должно быть бесконечным.
- Конечность не равна правильности результата: за правильность отвечает результативность.