Fibonacci Number

Q: Özyinelemeli Fibonacci fonksiyonunun zaman karmaşıklığı nedir?

Saf özyineleme 2 × F(n+1) - 1 çağrı yapar; bu sayı 1.618^n gibi büyür ve genellikle O(2^n) olarak yazılır. n = 45 için bu yaklaşık 3.7 × 10^9 çağrı demektir. Her sonucu bir tabloda ya da iki değişkende bir kez saklamak, bunu O(n) değerine düşürür.

Q: Fibonacci'yi dinamik programlamayla nasıl çözersiniz?

F(n) = F(n-1) + F(n-2) bağıntısıyla başlayın ve değerleri n artan sırayla hesaplayıp her birini saklayın. Bir tabloyu alttan üste doğru doldurabilir ya da özyinelemeli fonksiyonu koruyup sonuçlarını önbelleğe alabilirsiniz; buna memoization denir. Her iki durumda da her değer bir kez hesaplanır, dolayısıyla toplam iş O(n) olur.

Q: Fibonacci O(1) alan kullanılarak hesaplanabilir mi?

Evet. Her sayı yalnızca kendisinden önce gelen iki sayıya bağlıdır; bu nedenle iki değişken yeterlidir. Son iki değeri tutun ve her adımda onları ileri kaydırın. Böylece O(n) zaman ve O(1) ek alan kullanılır.

Q: O(n)'den daha hızlı bir yol var mı?

Evet. [[1, 1], [1, 0]] matrisinin n . kuvveti, sağ üst köşesinde F(n) değerini tutar ve ardışık kare alma işlemi bu kuvveti O(log n) matris çarpımıyla hesaplar. Altın oranın kuvvetlerini kullanan kapalı bir formül de vardır, ancak kayan noktalı sayılarla çalışır ve n büyüdükçe hassasiyet kaybeder; bu nedenle tamsayı yöntemleri tercih edilir.

BaşlangıçDinamik programlama Özyineleme

+10

Fibonacci sayıları F(0) = 0 ve F(1) = 1 ile başlar ve sonraki her sayı kendisinden önceki iki sayının toplamıdır: F(n) = F(n-1) + F(n-2). Dizi 0, 1, 1, 2, 3, 5, 8, 13 şeklinde başlar. Fonksiyonun n değerini alır ve F(n) değerini döndürür.

Fonksiyon

fib(n: integer) → integer

ninteger: 0'dan başlayarak sayıldığında Fibonacci dizisindeki konum
Döndürürinteger: Fibonacci sayısı F(n)

Kısıtlar

0 ≤ n ≤ 45
Yanıt, işaretli 32 bitlik bir tamsayıya sığar: F(45) = 1134903170.

Örnekler

Girdi: n = 4
Çıktı: 3
Açıklama: Başlangıçtan itibaren sayın: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2 ve F(4) = 2 + 1 = 3.

Girdi: n = 10
Çıktı: 55
Açıklama: 0 indeksinden başlayan dizi 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 şeklinde ilerler. 10. indeksteki sayı 34 + 21 = 55 olur.

Gönderirken +13 gizli test

Ek soru

F(n)'i O(log n) zamanda hesaplayabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Tanım zaten özyinelemeli bir fonksiyondur ve onu bu şekilde yazmak doğru cevabı verir. Tuzak, çalışma süresidir: iki özyinelemeli çağrı birbirlerinin yaptığı işi tekrarlar ve çağrı sayısı n ile üstel olarak artar. Dinamik programlama, her Fibonacci sayısını alttan üste doğru yalnızca bir kez hesaplayarak bunu çözer. Son adımda, sonraki sayının ihtiyaç duyduğu yalnızca iki sayı tutulur.

Doğrudan tanımdan özyineleme

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Tanımı kelimesi kelimesine çevirin. fib(0) 0'dır, fib(1) 1'dir ve daha büyük herhangi bir değer fib(n-1) + fib(n-2) döndürür. Her çağrı zinciri iki temel durumdan biriyle sona erer, bu nedenle yanıt doğrudur.

Şimdi çağrıları sayın. fib(5), fib(4) ve fib(3) çağrılarını yapar, ancak fib(4) da fib(3) çağrısını yapar. Sonuçta fib(3) iki kez, fib(2) üç kez ve fib(1) beş kez çalışır; fib(5) ise toplamda 15 çağrı yapar. Aynı değerler tekrar tekrar hesaplanır.

Çağrı sayısı Fibonacci sayılarını izler: F(n) hesaplanırken 2 × F(n+1) - 1 çağrı yapılır. n = 45 için bu yaklaşık 3.7 × 10^9 çağrı demektir; bir zaman sınırı için çok fazladır. Üst sınır genellikle O(2^n) şeklinde yazılır; kesin büyüme yaklaşık 1.618^n kadardır. Özyineleme yalnızca n düzey derinliğindedir, bu nedenle yığının O(n) alan kullanması gerekir.

Algoritma

n 0 veya 1 ise n değerini döndür.
Aksi hâlde, fonksiyonu n-1 ve n-2 değerleri için çağır.
İki sonucun toplamını döndür.

def fib(n):
    if n < 2:
        return n  # F(0) = 0, F(1) = 1
    return fib(n - 1) + fib(n - 2)

Bir tabloyu alttan üste doğru doldurun

Sezgi

Özyineleme yalnızca unuttuğu için yavaştır. Her Fibonacci sayısını ilk hesapladığında yazarsan, her biri tek bir toplama işlemine mal olur. 0'dan n'ye kadar olan indisler için yerler içeren bir f tablosu oluştur, f[0] = 0 ve f[1] = 1 olarak ayarla ve geri kalanını soldan sağa f[i] = f[i-1] + f[i-2] ile doldur.

İşe yaramasını sağlayan şey soldan sağa sıradır: f[i]'ye ulaştığında, ihtiyaç duyduğu iki sayı da zaten tablodadır. n = 10 için tablo 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 şeklinde dolar ve yanıt son hücrede olur.

Bu, en yalın hâliyle dinamik programlamadır: bir bağıntı ve daha küçük durumların yanıtlarından oluşan bir tablo. n-1 toplama işlemi, O(n) zaman gerekir ve tablo n + 1 sayı tutar; yani O(n) alan kullanır. n = 45 artık milyarlarca çağrı yerine 44 toplama işlemi gerektirir.

Algoritma

n 0 veya 1 ise n değerini döndür.
f[0] = 0 ve f[1] = 1 olacak şekilde n + 1 sayıdan oluşan bir tablo oluştur.
2'den n'ye kadar i için f[i] = f[i-1] + f[i-2] değerini ata.
f[n] değerini döndür.

def fib(n):
    if n < 2:
        return n
    f = [0] * (n + 1)  # f[i] will hold F(i)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

Yalnızca son iki sayıyı tut

Sezgi

Tablo döngüsünün ne okuduğuna bak. f[i] değerini doldurmak için f[i-1] ve f[i-2] gerekir; daha eski hiçbir değer gerekmez, dolayısıyla önceki tüm hücreler gereksizdir. Tablo yerine iki değişken tut: prev iki adım önceki sayıyı, curr ise bir adım önceki sayıyı tutar.

prev = 0 ve curr = 1 ile başla; bunlar F(0) ve F(1) değerleridir. Her adımda next = prev + curr hesapla, ardından ikiliyi ileri kaydır: prev eski curr değerini, curr ise next değerini alır. n = 4 için ikili (0, 1) değerinden (1, 1), (1, 2) ve (2, 3) değerlerine ilerler; yanıt curr = 3 olur.

İşlem sayısı yine n-1 toplama, zaman karmaşıklığı O(n) olur; bellekte üç tamsayı tutulur ve alan karmaşıklığı O(1) olur. Güncellemelerin sırası önemlidir: toplama yapmadan önce prev değerinin üzerine yazarsan, toplam yanlış değeri kullanır.

Algoritma

n 0 veya 1 ise n değerini döndür.
prev = 0 ve curr = 1 olarak ayarla.
n-1 kez tekrarla: next = prev + curr değerini hesapla, ardından prev = curr ve curr = next olarak ayarla.
curr değerini döndür.

def fib(n):
    if n < 2:
        return n
    prev, curr = 0, 1  # F(0) and F(1)
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr

Tuzaklar ve uç durumlar

Fibonacci, dinamik programlamanın klasik ilk problemidir ve hataların çoğu özyinelemeden ya da ilk iki değerden kaynaklanır.

Naif özyinelemeyi kullanmak. Küçük testleri geçer, ancak n = 45 için milyarlarca çağrı gerekir. Sonuçları bir tabloda ya da iki değişkende saklayın.
Başlangıcı yanlış belirlemek. Burada F(0) = 0 ve F(1) = 1, dolayısıyla F(2) = 1 ve F(10) = 55. Diziyi 1, 1 ile başlatmak her yanıtı bir indeks kaydırır.
Küçük n değerleri için kontrol eklemeden tablo oluşturmak. n = 0 için n + 1 = 1 boyutundaki tabloda f[1] için yer yoktur ve buraya yazmak sınırların dışına çıkar. n < 2 olduğunda doğrudan n döndürün.
İkiliyi yanlış sırayla güncellemek. prev = curr ve ardından curr = prev + curr yapmak, yeni prev değerini toplar ve curr değerini ikiye katlar. Önce toplamı next içine hesaplayın ya da dilde varsa eşzamanlı atama kullanın.
Bir adım fazla ilerlemek. F(n+1) değerini de hesaplayan bir döngü, sınırda F(46) = 1836311903 değerine ulaşır; bu değer yalnızca şans eseri 32 bite sığar. F(47) sığmaz.

Sıkça sorulan sorular4

Özyinelemeli Fibonacci fonksiyonunun zaman karmaşıklığı nedir?

Saf özyineleme 2 × F(n+1) - 1 çağrı yapar; bu sayı 1.618^n gibi büyür ve genellikle O(2^n) olarak yazılır. n = 45 için bu yaklaşık 3.7 × 10^9 çağrı demektir. Her sonucu bir tabloda ya da iki değişkende bir kez saklamak, bunu O(n) değerine düşürür.

Fibonacci'yi dinamik programlamayla nasıl çözersiniz?

F(n) = F(n-1) + F(n-2) bağıntısıyla başlayın ve değerleri n artan sırayla hesaplayıp her birini saklayın. Bir tabloyu alttan üste doğru doldurabilir ya da özyinelemeli fonksiyonu koruyup sonuçlarını önbelleğe alabilirsiniz; buna memoization denir. Her iki durumda da her değer bir kez hesaplanır, dolayısıyla toplam iş O(n) olur.

Fibonacci O(1) alan kullanılarak hesaplanabilir mi?

Evet. Her sayı yalnızca kendisinden önce gelen iki sayıya bağlıdır; bu nedenle iki değişken yeterlidir. Son iki değeri tutun ve her adımda onları ileri kaydırın. Böylece O(n) zaman ve O(1) ek alan kullanılır.

O(n)'den daha hızlı bir yol var mı?

Evet. [[1, 1], [1, 0]] matrisinin n. kuvveti, sağ üst köşesinde F(n) değerini tutar ve ardışık kare alma işlemi bu kuvveti O(log n) matris çarpımıyla hesaplar. Altın oranın kuvvetlerini kullanan kapalı bir formül de vardır, ancak kayan noktalı sayılarla çalışır ve n büyüdükçe hassasiyet kaybeder; bu nedenle tamsayı yöntemleri tercih edilir.