Сложность и затраты времени

Проведем анализ временных затрат для ханойских башен (и всех задач, сводящихся к решению двух подзадач размерности n-1). Подсчитаем требуемое число ходов T (n). С учетом структуры решения:

T (n) = +1.

Простое доказательство по индукции дает:

T (n) = -1 + -2 + … + 2 +1 = -1.

Можно показать, что последовательность ходов, реализуемая рекурсивным алгоритмом, является оптимальной, так что никакой другой алгоритм не может решить задачу за меньшее число ходов.

Алгоритм решения задачи о Ханойских башнях является конечным, так как все используемые циклы выполняются конечное число раз.

Сложность — количественная характеристика алгоритма, которая говорит о том, сколько времени он работает (временная сложность), либо о том, какой объем памяти он занимает (емкостная сложность). На практике сложность рассматривают как временную сложность.

Из определения сложности следует, что она зависит от размерности входных данных или, как говорят, от длины входа. В задаче о Ханойских башнях входными данными является число дисков.

Рассчитаем порядок временной сложности в соответствии с пошаговым алгоритмом.

Временная сложность процедуры будет зависеть от количества переносов, которое равно 2n-1, значит О (2n-1).