FIB

EN: FIB

Число Фибоначчи — элемент последовательности, заданной рекуррентностью F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2): 0, 1, 1, 2, 3, 5, 8, 13, … Наивное двойное рекурсивное вычисление F(n) работает за O(2ⁿ); мемоизация или итерация снижает это до O(n); возведение матриц в степень достигает O(log n).