Fibonacci Number

Q: Độ phức tạp thời gian của hàm Fibonacci đệ quy là bao nhiêu?

Đệ quy ngây thơ thực hiện 2 × F(n+1) - 1 lần gọi, con số này tăng theo 1.618^n và thường được viết là O(2^n) . Lưu mỗi kết quả một lần trong bảng hoặc trong hai biến giúp giảm độ phức tạp xuống O(n) .

Q: Tại sao thuật toán Fibonacci đệ quy chỉ dùng O(n) bộ nhớ?

Chỉ có một chuỗi lời gọi nằm trên ngăn xếp (stack) tại một thời điểm, và chuỗi sâu nhất chạy từ n , n-1 xuống đến 1. Một lời gọi giải phóng khung của nó khi trả về, vì vậy ngăn xếp không bao giờ chứa quá n khung, dù tổng số lời gọi tăng theo cấp số mũ.

Q: Làm thế nào để giải bài toán Fibonacci bằng quy hoạch động?

Tính các giá trị theo thứ tự tăng dần của n và lưu từng giá trị vào một bảng được điền từ dưới lên. Hoặc giữ nguyên hàm đệ quy và lưu vào bộ nhớ đệm các kết quả của hàm, cách này gọi là ghi nhớ hóa (memoization). Dù chọn cách nào, mỗi giá trị cũng chỉ được tính một lần, nên độ phức tạp là O(n) .

Người mớiQuy hoạch động Đệ quy

+10

Dãy Fibonacci bắt đầu bằng F(0) = 0 và F(1) = 1, mỗi số tiếp theo là tổng của hai số đứng trước nó: F(n) = F(n-1) + F(n-2). Dãy số bắt đầu bằng 0, 1, 1, 2, 3, 5, 8, 13. Hàm của bạn nhận n và trả về F(n).

Hàm

fib(n: integer) → integer

ninteger: vị trí trong dãy Fibonacci, tính từ 0
Trả vềinteger: số Fibonacci F(n)

Ràng buộc

0 ≤ n ≤ 45
Đáp án nằm trong phạm vi số nguyên có dấu 32 bit: F(45) = 1134903170.

Ví dụ

Đầu vào: n = 4
Đầu ra: 3
Giải thích: Đếm tăng dần từ đầu: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2 và F(4) = 2 + 1 = 3.

Đầu vào: n = 10
Đầu ra: 55
Giải thích: Dãy số bắt đầu từ chỉ số 0 là 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Số ở chỉ số 10 là 34 + 21 = 55.

Câu hỏi mở rộng

Bạn có thể tính F(n) trong thời gian O(log n) không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Định nghĩa đã là một hàm đệ quy (recursive function), và viết code theo cách đó sẽ cho đáp án đúng trong thời gian lũy thừa, vì hai lần gọi hàm lặp lại công việc của nhau. Quy hoạch động tính mỗi số đúng một lần, từ dưới lên. Mỗi số chỉ cần hai số đứng trước nó, nên chỉ cần hai biến.

Đệ quy đúng như định nghĩa

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Dịch định nghĩa: return fib(n-1) + fib(n-2), với fib(0) = 0 và fib(1) = 1. Mọi chuỗi lời gọi đều kết thúc ở một trường hợp cơ sở, nên đáp án đúng.

Các lời gọi lặp lại công việc. fib(5) chạy fib(3) hai lần, fib(2) ba lần và fib(1) năm lần, tổng cộng 15 lời gọi. Nói chung, F(n) cần 2 × F(n+1) - 1 lời gọi, khoảng 3.7 × 10^9 khi n = 45. Số lượng tăng theo 1.618^n, thường được viết là O(2^n). Ngăn xếp sâu n cấp, nên độ phức tạp không gian là O(n).

Thuật toán

Nếu n là 0 hoặc 1, hãy trả về n.
Nếu không, hãy gọi hàm với n-1 và n-2.
Trả về tổng của hai kết quả.

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

Điền vào bảng từ dưới lên

Ý tưởng

Đệ quy chạy chậm vì không ghi nhớ. Hãy ghi lại mỗi số ngay lần đầu tính số đó, mỗi số chỉ cần một phép cộng. Điền bảng từ trái sang phải: khi đến f[i], hai giá trị cần dùng đã có sẵn. Với n = 10, bảng có các giá trị 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Cách này cần n-1 phép cộng, thời gian O(n) và n + 1 ô nhớ, không gian O(n). Với n = 45, cách này chỉ cần 44 phép cộng thay vì hàng tỷ lần gọi hàm.

Thuật toán

Nếu n là 0 hoặc 1, trả về n.
Tạo một bảng gồm n + 1 số, với f[0] = 0 và f[1] = 1.
Với i từ 2 đến n, đặt f[i] = f[i-1] + f[i-2].
Trả về 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]

Chỉ giữ lại hai số cuối cùng

Ý tưởng

Việc điền f[i] chỉ đọc f[i-1] và f[i-2], nên mọi ô cũ hơn đều không cần thiết. Hãy giữ hai biến: prev, số cách lùi hai bước, và curr, số cách lùi một bước. Với n = 4, cặp số lần lượt chuyển từ (0, 1) thành (1, 1), (1, 2) rồi (2, 3), và curr = 3 là đáp án.

Số phép tính vẫn là n-1 phép cộng, thời gian O(n), bộ nhớ O(1).

Thuật toán

Nếu n là 0 hoặc 1, trả về n.
Đặt prev = 0 và curr = 1.
Lặp lại n-1 lần: tính next = prev + curr, sau đó đặt prev = curr và curr = next.
Trả về 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

Lỗi thường gặp và trường hợp biên

Nộp lời giải đệ quy ngây thơ. Cách này đúng, nhưng gọi hàm hàng tỷ lần khi n = 45.
Bắt đầu dãy số bằng 1, 1. Ở đây F(0) = 0, nên F(10) bằng 55, không phải 89.
Không kiểm tra trường hợp n nhỏ trong phiên bản dùng bảng. Với n = 0, bảng chỉ có một ô, nên ghi vào f[1] sẽ vượt quá giới hạn. Trả về n khi n < 2.
Cập nhật cặp giá trị sai thứ tự. prev = curr rồi đến curr = prev + curr sẽ làm curr tăng gấp đôi sau mỗi bước, nên n = 4 trả về 8. Hãy tính next trước hoặc dùng phép gán đồng thời.

Câu hỏi thường gặp3

Độ phức tạp thời gian của hàm Fibonacci đệ quy là bao nhiêu?

Đệ quy ngây thơ thực hiện 2 × F(n+1) - 1 lần gọi, con số này tăng theo 1.618^n và thường được viết là O(2^n). Lưu mỗi kết quả một lần trong bảng hoặc trong hai biến giúp giảm độ phức tạp xuống O(n).

Tại sao thuật toán Fibonacci đệ quy chỉ dùng O(n) bộ nhớ?

Chỉ có một chuỗi lời gọi nằm trên ngăn xếp (stack) tại một thời điểm, và chuỗi sâu nhất chạy từ n, n-1 xuống đến 1. Một lời gọi giải phóng khung của nó khi trả về, vì vậy ngăn xếp không bao giờ chứa quá n khung, dù tổng số lời gọi tăng theo cấp số mũ.

Làm thế nào để giải bài toán Fibonacci bằng quy hoạch động?

Tính các giá trị theo thứ tự tăng dần của n và lưu từng giá trị vào một bảng được điền từ dưới lên. Hoặc giữ nguyên hàm đệ quy và lưu vào bộ nhớ đệm các kết quả của hàm, cách này gọi là ghi nhớ hóa (memoization). Dù chọn cách nào, mỗi giá trị cũng chỉ được tính một lần, nên độ phức tạp là O(n).