Jelaskan function fib(n) dari Pemrograman dinamis

var previousFib := 0, currentFib := 1

repeat n − 1 times // loop is skipped if n = 1

var newFib := previousFib + currentFib

Dalam kedua contoh tersebut, kita hanya menghitung fib(2) satu kali, lalu gunakan untuk menghitung keduanya fib(4) dan fib(3), alih-alih menghitungnya setiap kali salah satu dari mereka dievaluasi.

Metode di atas sebenarnya membutuhkan  waktu untuk n besar karena penjumlahan dua bilangan bulat dengan  bit masing-masing mengambil  waktu. (Nomor nth fibonacci memiliki  bit.) Juga, ada bentuk tertutup untuk deret Fibonacci, yang dikenal sebagai rumus Binet, yang darinya suku -th dihitung kira-kira  waktu, yang lebih efisien daripada teknik pemrograman dinamis di atas. Namun, pengulangan sederhana secara langsung memberikan bentuk matriks yang mengarah ke perkiraan  algoritma dengan eksponensial matriks cepat.