130
правок
Изменения
→Сравнение с рекурсивным алгоритмом
==Сравнение с рекурсивным алгоритмом==
Главным приемуществом алгоритма Джонсона-Троттера является то, что нам не нужно хранить все предыдущие перестановки (из <tex>n - 1</tex> элемента), а только текущую. Следовательно, этот алгоритм потребляет только <tex>O(n)</tex> памяти. Также, из-за нерекурсивности этот алгоритм работает быстрее. Это можно строго доказать, но доказательство довольно громозодкое и приводить его мы здесь не будем.
