Fibonacci Number

Q: Apa kompleksitas waktu dari fungsi Fibonacci rekursif?

Rekursi naif membuat 2 × F(n+1) - 1 pemanggilan, jumlah yang bertambah seperti 1.618^n dan biasanya ditulis O(2^n) . Menyimpan setiap hasil satu kali, dalam tabel atau dalam dua variabel, menurunkan kompleksitasnya menjadi O(n) .

Q: Mengapa Fibonacci rekursif hanya menggunakan ruang O(n)?

Hanya satu rantai pemanggilan yang berada di stack pada satu waktu, dan rantai terdalam menjalankan n , n-1 , hingga 1. Sebuah pemanggilan membebaskan frame-nya saat kembali, sehingga stack tidak pernah menampung lebih dari n frame, meskipun jumlah total pemanggilannya bersifat eksponensial.

Q: Bagaimana cara menyelesaikan Fibonacci dengan pemrograman dinamis?

Hitung nilai secara berurutan, dari yang terkecil hingga terbesar, berdasarkan n , lalu simpan setiap nilai dalam tabel yang diisi dari bawah ke atas. Atau, pertahankan fungsi rekursif dan cache hasilnya. Cara ini disebut memoization. Dengan kedua cara tersebut, setiap nilai dihitung satu kali, sehingga kompleksitasnya O(n) .

PemulaDynamic programming Rekursi

+10

Bilangan Fibonacci dimulai dengan F(0) = 0 dan F(1) = 1, lalu setiap bilangan berikutnya adalah jumlah dari dua bilangan sebelumnya: F(n) = F(n-1) + F(n-2). Urutannya dimulai dengan 0, 1, 1, 2, 3, 5, 8, 13. Fungsimu menerima n dan mengembalikan F(n).

Fungsi

fib(n: integer) → integer

ninteger: posisi dalam urutan Fibonacci, dihitung mulai dari 0
Mengembalikaninteger: bilangan Fibonacci F(n)

Batasan

0 ≤ n ≤ 45
Jawabannya muat dalam bilangan bulat bertanda 32-bit: F(45) = 1134903170.

Contoh

Input: n = 4
Output: 3
Penjelasan: Hitung naik dari awal: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2, dan F(4) = 2 + 1 = 3.

Input: n = 10
Output: 55
Penjelasan: Urutan dari indeks 0 adalah 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Angka pada indeks 10 adalah 34 + 21 = 55.

Pertanyaan lanjutan

Bisakah kamu menghitung F(n) dalam waktu O(log n)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Definisinya sudah berupa fungsi rekursif, dan mengodekannya seperti itu memberikan jawaban yang benar dalam waktu eksponensial karena kedua pemanggilan mengulangi pekerjaan satu sama lain. Pemrograman dinamis menghitung setiap angka sekali, dari bawah ke atas. Setiap angka hanya membutuhkan dua angka sebelumnya, jadi dua variabel sudah cukup.

Rekursi langsung dari definisinya

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Terjemahkan definisinya: return fib(n-1) + fib(n-2), dengan fib(0) = 0 dan fib(1) = 1. Setiap rangkaian pemanggilan berakhir pada kasus dasar, jadi jawabannya benar.

Pemanggilan fungsi mengulang pekerjaan. fib(5) menjalankan fib(3) dua kali, fib(2) tiga kali, dan fib(1) lima kali, total 15 pemanggilan. Secara umum, F(n) membutuhkan 2 × F(n+1) - 1 pemanggilan, sekitar 3.7 × 10^9 pada n = 45. Jumlahnya bertambah seperti 1.618^n, biasanya ditulis O(2^n). Stack memiliki kedalaman n level, jadi penggunaan ruangnya O(n).

Algoritma

Jika n bernilai 0 atau 1, kembalikan n.
Jika tidak, panggil fungsi dengan n-1 dan n-2.
Kembalikan jumlah kedua hasil tersebut.

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

Isi tabel dari bawah ke atas

Intuisi

Rekursi berjalan lambat karena melupakan hasil. Catat setiap angka saat pertama kali kamu menghitungnya, dan setiap angka hanya memerlukan satu penjumlahan. Isi tabel dari kiri ke kanan: saat kamu mencapai f[i], kedua nilai yang dibutuhkannya sudah tersedia. Untuk n = 10, isi tabelnya adalah 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Jumlahnya adalah n-1 penjumlahan, waktu O(n), dan n + 1 slot, ruang O(n). n = 45 memerlukan 44 penjumlahan, bukan miliaran pemanggilan.

Algoritma

Jika n adalah 0 atau 1, kembalikan n.
Buat tabel berisi n + 1 angka dengan f[0] = 0 dan f[1] = 1.
Untuk i dari 2 hingga n, tetapkan f[i] = f[i-1] + f[i-2].
Kembalikan f[n].

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]

Hanya sisakan dua angka terakhir

Intuisi

Mengisi f[i] hanya membaca f[i-1] dan f[i-2], jadi setiap slot yang lebih lama tidak berguna. Pertahankan dua variabel: prev, angka dari dua langkah sebelumnya, dan curr, angka dari satu langkah sebelumnya. Untuk n = 4, pasangan bergerak dari (0, 1) ke (1, 1), (1, 2), lalu (2, 3), dan curr = 3 adalah jawabannya.

Jumlah pekerjaannya tetap sama, yaitu n-1 penjumlahan, dengan waktu O(n) dan ruang O(1).

Algoritma

Jika n adalah 0 atau 1, kembalikan n.
Tetapkan prev = 0 dan curr = 1.
Ulangi sebanyak n-1 kali: hitung next = prev + curr, lalu tetapkan prev = curr dan curr = next.
Kembalikan curr.

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

Jebakan dan kasus tepi

Mengumpulkan rekursi naif. Cara ini benar, tetapi membuat miliaran pemanggilan pada n = 45.
Memulai urutan dengan 1, 1. Di sini F(0) = 0, jadi F(10) adalah 55, bukan 89.
Tidak ada pemeriksaan untuk n kecil pada versi tabel. Untuk n = 0, tabel memiliki satu slot, jadi menulis f[1] berada di luar batas. Kembalikan n saat n < 2.
Memperbarui pasangan dalam urutan yang salah. prev = curr diikuti oleh curr = prev + curr menggandakan curr pada setiap langkah, sehingga n = 4 menghasilkan 8. Hitung next terlebih dahulu, atau gunakan penugasan simultan.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari fungsi Fibonacci rekursif?

Rekursi naif membuat 2 × F(n+1) - 1 pemanggilan, jumlah yang bertambah seperti 1.618^n dan biasanya ditulis O(2^n). Menyimpan setiap hasil satu kali, dalam tabel atau dalam dua variabel, menurunkan kompleksitasnya menjadi O(n).

Mengapa Fibonacci rekursif hanya menggunakan ruang O(n)?

Hanya satu rantai pemanggilan yang berada di stack pada satu waktu, dan rantai terdalam menjalankan n, n-1, hingga 1. Sebuah pemanggilan membebaskan frame-nya saat kembali, sehingga stack tidak pernah menampung lebih dari n frame, meskipun jumlah total pemanggilannya bersifat eksponensial.

Bagaimana cara menyelesaikan Fibonacci dengan pemrograman dinamis?

Hitung nilai secara berurutan, dari yang terkecil hingga terbesar, berdasarkan n, lalu simpan setiap nilai dalam tabel yang diisi dari bawah ke atas. Atau, pertahankan fungsi rekursif dan cache hasilnya. Cara ini disebut memoization. Dengan kedua cara tersebut, setiap nilai dihitung satu kali, sehingga kompleksitasnya O(n).