ผลต่างระหว่างรุ่นของ "จำนวนฟีโบนัชชี"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล →รูปเมทริกซ์: มันต้องอย่างนี้แหละ |
|||
บรรทัด 98:
:<math>\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.</math>
ด้วยรูปปิดดังกล่าว การคำนวณค่าฟีโบนัชชีจึงสามารถคำนวณได้โดยใช้จำนวนการดำเนินการเลขคณิต O(log ''n'') หรือใช้เวลา O(''M''(''n'') log(''n'')) โดยที่ ''M''(''n'') คือเวลาในการคูณเลข ''n'' หลัก 2 ตัว<ref>{{citation|title=In honour of Fibonacci|first=Edsger W.|last=Dijkstra|authorlink=Edsger W. Dijkstra|year=1978|url=http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF}}.</ref> โดยใช้วิธี[[การยกกำลังโดยการยกกำลัง
:<math> x^n=
\begin{cases}
| |||