فیبوناتچی از مرتبه log n

O log( n ) for fibonacci

با سلام.
الگوریتم محاسبه دنباله فیبوناتچی در روش معمول از مرتبه نمایی یا مرتبه n حل میشوند.اما اینجا روشی را معرفی میکنم که این مساله را با الگوریتمی از مرتبه log n حل میکند.

یک روش ، روش heapfibo است.این pdf ها را مطالعه کنید.

روش دیگر ارائه یک فرمول سریعتر برای حل رابطه بازگشتی است. 

اینجارا مطالعه کنید 

یا این را بخوانید
.

function fib(n)
  i=1; j=0; k=0; h=1;
  while n>0 do 
     if n is odd then 
               t=jh;
               j=ih+jk+t;
               i=ik+t;
     t=h^2;
     h=2kh+t;
     k=k^2+t
     n=n div 2;
  return j