Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...
Her terimi kendinden önceki iki terimin toplamı olan diziyi recursive veya tabulation ile hesaplar.
DSA kaynağı Fibonacci algoritmasını recursion örneği olarak verir: n değeri taban durumdaysa doğrudan döndürülür, aksi halde Fibonacci(n-1) ve Fibonacci(n-2) çağrılır. Aynı kaynak bu recursive sürümün çok hızlı büyüyen çağrı ağacı nedeniyle verimsiz olduğunu özellikle vurgular.
Dinamik programlama yaklaşımı, aynı alt problemleri tekrar tekrar çözmek yerine önceki iki değeri saklayarak ilerler. Bu sayede exponential recursive maliyet O(n) zamana ve O(1) alana indirilebilir.
Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.
1function fibonacci(n: number): number {2 if (n < 0) { throw new Error('n must be non-negative'); }3 if (n <= 1) { return n; }4 let previous = 0, current = 1;5 for (let index = 2; index <= n; index += 1) {6 const next = previous + current;7 previous = current;8 current = next;9 }10 return current;11}0 ile 50 arasında bir n değeri girin. Örnek: 10
0 ile 50 arasında bir n değeri girin. Örnek: 10
En İyi Durum: O(1)
Ortalama Durum: O(n)
En Kötü Durum: O(n)
O(1) - Giriş boyutu ne olursa olsun, algoritma her zaman aynı sürede çalışır.
Fibonacci Sequence Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar: