Kompleksitas algoritma Fibonacci rekursif

Menggunakan algoritma Fibonacci rekursif berikut:

def fib(n):
   if n==0:
      return 0
   elif n==1
      return 1
   return (fib(n-1)+fib(n-2))

Jika saya memasukkan angka 5 untuk menemukan fib (5), saya tahu ini akan menghasilkan 5 tetapi bagaimana saya memeriksa kompleksitas algoritma ini? Bagaimana cara menghitung langkah-langkah yang terlibat?

Sebagian besar waktu, Anda dapat mewakili algoritma rekursif menggunakan persamaan rekursif. Dalam hal ini persamaan rekursif untuk algoritma ini adalah . Kemudian Anda bisa menemukan bentuk persamaan yang tertutup menggunakan metode substitusi atau metode ekspansi (atau metode lain yang digunakan untuk menyelesaikan perulangan). Dalam hal ini Anda mendapatkan T ( n ) = Θ ( ϕ n ) , di mana$T(n) = T(n-1) + T(n-2) + \Theta(1)$$T(n) = \Theta(\phi^n)$$\phi$adalah rasio emas ( ).$\phi = \frac{(1 + \sqrt{5})}{2}$

Jika Anda ingin mengetahui lebih lanjut tentang cara mengatasi rekurensi, saya sangat menyarankan Anda untuk membaca bab 4 dari Pengantar Algoritma .

sebagai alternatif untuk pengulangan hubungan / analisis matematika (tapi bukan pengganti ) latihan empiris sederhana, tampaknya tidak diajarkan sangat sering di kelas tetapi sangat informatif, adalah untuk menghitung # eksekusi fungsi, dan kemudian grafik hitungan untuk rentang input n kecil , dan kemudian kurva sesuai hasilnya. hasil umumnya akan cocok dengan pendekatan matematika teoretis.

materi pendukung yang baik untuk latihan ini dapat ditemukan di bab 3 online gratis, waktu yang berjalan dari algoritma / Yayasan Ilmu Komputer , Ullman

Hasil dari fib (n) adalah jumlah dari semua panggilan rekursif yang dikembalikan 1. Oleh karena itu ada persis fib (n) panggilan rekursif mengevaluasi fib (1). Jadi waktu eksekusi adalah Ω (fib (n)); Anda harus menunjukkan bahwa panggilan yang mengembalikan 0 dan panggilan rekursif lainnya tidak menambah signifikan hal ini.

Alasan yang sama akan berlaku untuk fungsi yang didefinisikan secara rekursif yang mengembalikan 1, atau 0, atau hasil dari panggilan rekursif lain.

$T(n)=T(n-1)+T(n-2)$ $T(n)>2T(n-2)$$T(n-1)>T(n-2)$$T(n)= \Omega(c^{n})$