Thắc mắc về độ phức tạp của thuật toán tính số Fibonacci

[thyphan]

Em xin chào tất cả mọi người,

Em đang đọc về thuật toán tính số Fib trong sách CTDL&GT của thầy Nguyễn Đức Nghĩa (trang 26). Em cảm thấy không hiểu một vài chỗ mong nhận được sự hướng dẫn từ mọi người ạ:

1. Từ công thức Muavre đã cho sách tính như thế nào lại thu được số bit biểu diễn fk = theta(k) vậy ạ. Em thấy khai triển ra k chỉ xuất hiện ở số mũ, vậy mà kết quả ra theta(k), em không nghĩ ra được.
2. Ở công thức tính thời gian của Fibiter: tổng xích ma chạy từ k = 1 đến n. Em lại nghĩ k chạy từ 2 --> n chứ ạ (theo vòng for), nếu em sai mong mọi người chỉ ra cái sai của em.
3. Lúc đầu sách viết thời gian tính theo các phép toán số học là theta(n), còn câu kết luận tính theo số bit là theta(n^2). Chỗ này làm em bối rối quá, không biết phải tính theo cái nào.

Cảm ơn mọi người đã đọc những câu hỏi của em.

[rogp10]

1. Do |\frac{1-\sqrt 5}{2}| < 1 nên |\frac{1-\sqrt 5}{2}|^k < 1. Như vậy f_k \in \Theta(\phi^k) với \phi là tỉ lệ vàng, nên \log_2 f_k \in \Theta(k).
2. 1*c (khởi tạo) + sigma.
3. Đó là hai cách tính, mà tính theo bit (bit complexity) thì sát với thực tế hơn.

[thyphan]

1. Anh cho em hỏi log2(fk) = theta(k) làm sao suy ra fk = theta(k) anh nhỉ
2. đoạn này em vẫn chưa hiểu lắm
3. Cho em xin tên tài liệu/ kiến thức cần học để em cải thiện sự tính toán theo bit complexity với ạ (em thấy mình yếu phần này, em cảm ơn anh đã trả lời em )

[tntxtnt]

1. Ý tác giả là số Fibonacci thứ k sẽ là 1 số có số bit cỡ \Theta(k) bit. Hay nôm na là số Fibonacci thứ k sẽ có \Theta(k) chữ số ấy :V
   Ví dụ:

   • f_{100} = 354224848179261915075 có 21 chữ số
   • f_{200} = 280571172992510140037611932413038677189525 có 42 chữ số
   • f_{300} = 222232244629420445529739893461909967206666939096499764990979600 có 63 chữ số

   thì thấy rõ là k tăng 2 lần thì số chữ số cũng tăng 2 lần, k tăng 3 lần thì số chữ số cũng tăng 3 lần v.v… nên nói số Fibonacci thứ k sẽ có \Theta(k) chữ số. Với k lớn thế này thì phép toán tính tổng f_k + f_{k+1} sẽ ko còn là \Theta(1) nữa, mà là tỉ lệ thuận với số chữ số của f_k, hay là \Theta(k).

   số chữ số với số bit cũng tương tự thôi :V Số chữ số thì biểu diễn ở hệ thập phân, số bit biểu diễn ở hệ nhị phân. Tác giả nói rõ số bit biễu diễn của f_k là \Theta(k) chứ có nói f_k = \Theta(k) chỗ nào đâu :V :V

   chứng minh thì dùng công thức Muavre đó. Ví dụ muốn tìm số chữ số của f_{100} thì ta lấy \log_{10}(f_{100}) = 20.5492 nên f_{100} sẽ có 21 chữ số. Lấy \log_2 thay cho \log_{10} sẽ được số bit. Từ công thức Muavre, lấy \log_2(f_k) được k + vài hằng số nào đó nên \log_2(f_k) = \Theta(k), nên nói số bit biễu diễn của f_k là \Theta(k).

2. 1 tới n hay 2 tới n cũng được :V ko ảnh hưởng mấy tới kết quả cuối cùng. Nếu xét kĩ thì gán i = 0, j = 1 cũng tốn O(1) = O(k) vì ở đây k nhỏ k = 1 bit :V

3. Là do ban đầu mặc định số bit là cố định, ví dụ tính toán i, j trên kiểu int thì số bit cố định, ví dụ là 32-bit, nên 1 phép tính cộng / trừ dù có độ phức tạp là O(số bit của int) nhưng vì ở đây số bit cố định nên có thể xem nó là hằng số, nên cho là O(1), nên thời gian tính của hàm trên là \Theta(n). Nếu i, j có kiểu là kiểu số lớn bất kì thì số bit của i, j ko còn cố định nữa, nên đpt của phép tính cộng / trừ i, j là O(số bit của i, j), mà đã chứng minh ở trên số bit của i, j là \Theta(k) nên tổng cuối thành \Theta(n^2) :V

Cần nói rõ hơn là bài toán này có 2 biến: 1 là n là số Fibo thứ n cần tính, 2 là b là số bit của số nguyên :V Do chứng minh được b = \Theta(n) nên kết quả cuối cùng là \Theta(n^2), nếu ko thì là \Theta(bn) rồi. Nếu b là hằng số thì \Theta(bn) = \Theta(n), nếu b là biến có độ lớn \Theta(n) thì \Theta(bn) = \Theta(n*n) = \Theta(n^2).

Với cái bài toán khác thì cũng có biến b là số bit của kiểu dữ liệu cần tính toán nhưng đa số tính với kiểu số nguyên có kích cỡ cố định nên biến b ko còn là biến nữa mà trở thành hằng số b, mà là hằng số nên thường bị bỏ qua ko nhắc đến :V

Edit nữa: máy tính cũng ko phải thần thánh gì đâu, cộng số x với số y nó cũng cộng bit ở từng cột với nhau lại, nên phép cộng luôn tốn thời gian \Theta(b) chứ ko phải \Theta(1) đâu :V Do int có số bit cố định nên mới có thể nói \Theta(b) là \Theta(1)

[thyphan]

em cảm ơn anh đã dành thời gian trả lời câu hỏi em. Em cảm thấy rất được mở mang đầu óc.

[thyphan]

Em xin chân thành cảm ơn anh Rogp10 và Tntxtnt.

Edit: hôm nay tìm tài liệu đọc thì em tìm ra công thức tính số chữ số k của số n với hệ là b (đã học ở môn toán rời rạc, mà em lại quên hic hic). Em viết ra để có ai lỡ quên như em vào đọc lại luôn.

n, b: số nguyên dương, b >= 2,
Với mọi n nguyên, n có k chữ số hệ b:
b^(k-1) <= n < b^k
–> k -1 <= logb(n) < k (logarit cơ số b của n)
–> k = logb(n) + 1 (logb(n) làm tròn xuống)
Vd: 18 ứng với 10010 hệ 2, log2(18) + 1 = 4 + 1 = 5 nên 18 có 5 chữ số hệ 2 (5 bit)
log10(18) + 1 = 1 + 1 = 2 nên 18 có 2 chữ số hệ 10
(em cài mấy extension để gõ công thức toán nhưng ngồi loay hoay không dùng được, mọi người thông cảm )

[rogp10]

DNH dùng KaTeX dựa trên TeX
Để kích hoạt thì đặt code TeX giữa hai $ $ hoặc dùng cú pháp multiline $$<xuống dòng> ... <xuống dòng>$$