��: �� .

�� O(logn).

�� .

F_n = F_(n-1) + F_(n-2) F_(n+1) = F_n + F_(n-1) = 2*F_(n-1) + F_(n-2)

�� , � �� :

��

 | F_n    |        | 1   1 |   | F_(n-2)|
 |        |   =    |       |   |        |
 | F_(n+1)|        | 1   2 |   | F_(n-1)|.

�� A ��

     | 1   1 |
 A = |       |
     | 1   2 |,

��

 | F_(2n)  |             | 1 |
 |         |   =  A^n *  |   |
 | F_(2n+1)|             | 1 |.

��, �� 2n-�/2n+1-� �� , �� A �� n-�� , � �� O(log n) �� (�� /�� A � �� n).

P.S �� n-�� :

�� , �� log n ��, �� n-� ��. � �� , �� . �� .