3622
правки
Изменения
м
→Подсчет чисел Каталана
==Подсчет чисел Каталана==
Числа Каталана просто посчитать с помощью рекуррентной формулы. Для этого понадобится <tex dpi = 120>O(n)</tex> памяти и <tex dpi = 120>O(n^2)</tex> времени. За <tex dpi = 120>O(n)</tex> времени их можно посчитать , если использовать аналитическую формулу. Также из аналитической формулы можно выразить простую реккурентную формулу:
<tex dpi = 135> C_n = \frac{4n-2}{n+1} C_{n-1} </tex>.
