1.12. НЕСКОЛЬКО ЗАМЕЧАНИЙ ОТНОСИТЕЛЬНО СЛОЖНОСТИ

Всякое обсуждение алгоритмов должно затрагивать проблемы вычислительной сложности и потому, излагая какой-либо алгоритм, мы всегда будем стараться давать некоторое представление о времени и пространстве, необходимых для его реализации. Я хотел бы в этой связи отметить одну ошибку, которую часто совершают многие студенты: речь идет о смешении вычислительной сложности и сложности программирования. Длина программы, реализующей алгоритм, в принципе, мало связана с быстротой его выполнения и даже с требованиями к памяти. Если какая-то связь и существует, то она скорее имеет противоположный характер. «Сложные» алгоритмы обычно быстрее «простых». Так, (нерекурсивная) программа для выполнения быстрого преобразования Фурье и длиннее, и логически сложнее, чем программа, реализующая формулу суммирования этого преобразования,

однако выполняется она много быстрее. Подобные примеры являют нам и алгоритмы сортировки.

Часто представляется заманчивым использовать рекурсивное представление алгоритма, поскольку оно много короче нерекурсивного, а число операций в обоих случаях одинаково. При этом не следует забывать о высокой стоимости рекурсивных обращений, необходимости устройства для хранения содержимого регистров и т. д. Если число подобных обращений невелико по сравнению с числом прочих операций, то эти затраты вполне могут быть оправданы простотой получаемой в результате программы. В противном случае нерекурсивное представление позволяет получать более эффективные программы.

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