30/09/2018, 17:06
Cách tính độ phức tạp của thuật toán Fibonacci và Euclid?
Cách Cách không hiểu cách tính độ phức tạp của 2 thuật toán này, mong được các vị cao thủ võ lâm giảng giải chi tiết ạ.
Xin đa tạ…
Thuật toán trong bí kíp võ công của Double Space đây ạ:
Fibonacci
Function Fibonacci(n: integer): integer;
Begin
If n<2 then Fibonacci := n
Else Fibonacci := Fibonacci(n-1) + Fibonacci(n-2);
End;
Độ phức tạp: O(((1+sqrt(5))/2)^n)
Euclid
Function Euclid(m,n: integer): integer;
Var r: integer;
Begin
r := m mod n;
While r <> 0 do
Begin
m := n;
n := r;
r := m mod n;
End;
Euclid := n;
End;
Độ phức tạp: O(logarit n cơ số 2)
Bài liên quan
Fibonacci thì có thể tính số fibo thứ n trong O(log n);
Còn Euclid thì O(log max(A,B))
Cách Cách ko hiểu cách tính ạ
Lúc nãy em không thấy code của bác sr bác nhé
Mà rốt cục bác hỏi là thuật toán hay độ phức tạp
tất nhiên là độ phức tạp rồi ạ, cách tính ấy ạ. tuần sau phải lên lớp thuyết trình nên cần hiểu rõ ạ
Bác tham khảo cái Euclid ở đây
http://vnalgo.com/category/so-hoc/
sao trong này cái Euclid lại liên quan Fibonacci vậy ạ?
Định Lý đả chứng minh cái này em cũng biết chấp nhận thôi!
e cần hiểu để thuyết trình
Mình đả tận lực :’( Cái này ngoài tầm của em rồi!
Cách Cách ta sẽ chờ thêm cao thủ võ lâm vào giúp vậy. chứ ta đọc mãi không hiểu gì.
nên hiểu độ phức tạp là một cây thước để đánh giá mức độ “phức tạp” của thuật toán đó khi input được thêm vào.
vi.wikipedia.org
bạn nên nêu những điều bạn đã tìm hiểu được để dễ thảo luận với nhau. Bắt đầu từ chưa có gì thì hơi khó.
Độ phức tạp thuật toán
Thời gian mà máy tính khi thực hiện một thuật toán không chỉ phụ thuộc vào bản thân thuật toán đó, ngoài ra còn tùy thuộc từng máy tính. Để đánh giá hiệu quả của một thuật toán, có thể xét số các phép tính phải thực hiện khi thực hiện thuật toán này. Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Vì thế độ phức tạp thuật toán là một hàm phụ thuộc đầu vào. Tuy nhiên trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này mà ...
e không hiểu cách tính độ phức tạp nên không có gì cả ạ, nên e mới lên đây hỏi cách tính ạ.
cái độ phức tạp của thuật toán Fibonacci:
T(n)=T(n-1)+T(n-2)
, người ta bảo là T(n) tăng theo hàm số mũ a^n. tại sao lại thế ạ?rồi sau đó người ta cho
a^n=a^(n-1) + a^(n-2)
Bạn nghiên cứu thử 2 bài này xem, thấy có hình vẽ, khả năng là dễ hiểu
https://sites.google.com/site/quanghd/home/danh
http://tek.eten.vn/danh-gia-do-phuc-tap-thuat-toan
mình tìm ra 2 trang này rồi bạn. nhưng nó nói đại khái quá. mình vừa xem lại vở toán rời rạc thì cũng ra đc rôi.