30/09/2018, 17:06

Cách tính độ phức tạp của thuật toán Fibonacci và Euclid?

Cách Cách không hiểu cách tính độ phức tạp của 2 thuật toán này, mong được các vị cao thủ võ lâm giảng giải chi tiết ạ.
Xin đa tạ…

Thuật toán trong bí kíp võ công của Double Space đây ạ:

Fibonacci

Function Fibonacci(n: integer): integer;
Begin
    If n<2 then Fibonacci := n
    Else Fibonacci := Fibonacci(n-1) + Fibonacci(n-2);
End;

Độ phức tạ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 tạp: O(logarit n cơ số 2)

Code Lúc Hừng Đông viết 19:22 ngày 30/09/2018

Fibonacci thì có thể tính số fibo thứ n trong O(log n);
Còn Euclid thì O(log max(A,B))

Sáng Béo viết 19:18 ngày 30/09/2018

Cách Cách ko hiểu cách tính ạ

Code Lúc Hừng Đông viết 19:18 ngày 30/09/2018

Lúc nãy em không thấy code của bác sr bác nhé

Code Lúc Hừng Đông viết 19:17 ngày 30/09/2018

Mà rốt cục bác hỏi là thuật toán hay độ phức tạp

Sáng Béo viết 19:14 ngày 30/09/2018

Mà rốt cục bác hỏi là thuật toán hay độ phức tạp

tất nhiên là độ phức tạp rồi ạ, cách tính ấy ạ. tuần sau phải lên lớp thuyết trình nên cần hiểu rõ ạ

Code Lúc Hừng Đông viết 19:08 ngày 30/09/2018

Bác tham khảo cái Euclid ở đây
http://vnalgo.com/category/so-hoc/

Sáng Béo viết 19:15 ngày 30/09/2018

sao trong này cái Euclid lại liên quan Fibonacci vậy ạ?

Code Lúc Hừng Đông viết 19:10 ngày 30/09/2018

Định Lý đả chứng minh cái này em cũng biết chấp nhận thôi!

Sáng Béo viết 19:13 ngày 30/09/2018

Đị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 trình

Code Lúc Hừng Đông viết 19:07 ngày 30/09/2018

Mình đả tận lực :’( Cái này ngoài tầm của em rồi!

Sáng Béo viết 19:19 ngày 30/09/2018

Cách Cách ta sẽ chờ thêm cao thủ võ lâm vào giúp vậy. chứ ta đọc mãi không hiểu gì.

Minh Hoàng viết 19:19 ngày 30/09/2018

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.
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ó.

vi.wikipedia.org

Độ 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à ...

Sáng Béo viết 19:15 ngày 30/09/2018

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

e không hiểu cách tính độ phức tạp nên không có gì cả ạ, nên e mới lên đây hỏi cách tính ạ.

Sáng Béo viết 19:20 ngày 30/09/2018

cái độ phức tạp của thuật toán Fibonacci: T(n)=T(n-1)+T(n-2), người ta bảo là T(n) tăng theo hàm số mũ a^n. tại sao lại thế ạ?
rồi sau đó người ta cho a^n=a^(n-1) + a^(n-2)