Изменения

Время работы данного алгоритма в худшем случае <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество путей в графе из <tex>s</tex> в <tex>t</tex>. Например, на следующем графе данный алгоритм будет иметь время работы <tex>O(2^{n/2})</tex>. Если же использовать метод динамичекого программиования, речь о котором пойдет ниже, то асимптотику можно улучшить до <tex>O(n)</tex>.

[[Файл:Dp-countpaths-example.png‎|600px| Пример графа, на котором алгоритм имеет время работы <tex>O(2^{n/2})</tex>]]