Thư Viện Câu Hỏi Phỏng Vấn
Tổng hợp các câu hỏi tuyển dụng thực tế theo nhiều cấp độ từ Entry đến Expert để bạn tự tin chinh phục nhà tuyển dụng.
01
So sánh các cách tính số Fibonacci thứ N bằng Đệ quy thường, Quy hoạch động, và Nhân ma trận về mặt độ phức tạp thời gian và không gian?
Có 3 phương pháp phổ biến để tính số Fibonacci thứ N với hiệu năng khác nhau rõ rệt:
- Đệ quy thông thường:
- Cơ chế: Gọi đệ quy song song
F(n) = F(n-1) + F(n-2). - Hiệu năng: Tốn O(2^n) thời gian vì tính lại các bài toán con trùng lặp quá nhiều. Tốn O(n) không gian cho Stack đệ quy.
- Cơ chế: Gọi đệ quy song song
- Quy hoạch động (DP - Iterative):
- Cơ chế: Lưu 2 giá trị Fibonacci trước đó và tính tiến lên bằng vòng lặp.
- Hiệu năng: Tốn O(n) thời gian (chỉ duyệt 1 vòng lặp) và O(1) không gian (chỉ lưu 2 biến tạm).
- Nhân ma trận (Matrix Exponentiation):
- Cơ chế: Dựa trên công thức toán học luỹ thừa ma trận [ [1, 1], [1, 0] ]^n. Ta tính luỹ thừa bằng phương pháp Chia để trị (Binary Exponentiation).
- Hiệu năng: Tốn O(log n) thời gian và O(log n) không gian (hoặc O(1) nếu lặp). Cực kỳ hữu ích khi N rất lớn (vài tỷ).
.png)
.png)