Có thể viết một hàm Fibonacci để thực thi trong thời gian O(1) không?
Có thể viết một hàm Fibonacci để thực thi trong thời gian O(1) không?
Có thể tính Fibonacci rất nhanh, nhưng "O(1)" đúng nghĩa chỉ trong ngữ cảnh hạn chế:
F(0..92) (vừa int64) → O(1) thời gian, O(1) bộ nhớ hằng với giới hạn n.F(n) = round(φⁿ/√5) — O(1) phép toán số thực, nhưng sai số khi n lớn (≈ n > 70 với double); với số lớn chính xác cần tính luỹ thừa số lớn nên không còn O(1).Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.