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

htwap · May 9, 2015, 8:28am

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_Luc_H_ng_Dong · May 9, 2015, 8:20am

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

htwap · May 9, 2015, 8:24am

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

Code_Luc_H_ng_Dong · May 9, 2015, 8:25am

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

Code_Luc_H_ng_Dong · May 9, 2015, 8:26am

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

htwap · May 9, 2015, 8:29am

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_Luc_H_ng_Dong · May 9, 2015, 8:37am

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

htwap · May 9, 2015, 8:43am

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

Code_Luc_H_ng_Dong · May 9, 2015, 8:48am

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

htwap · May 9, 2015, 8:57am

e cần hiểu để thuyết trình

Code_Luc_H_ng_Dong · May 9, 2015, 8:58am

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

htwap · May 9, 2015, 8:59am

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

Rok_Hoang · May 9, 2015, 9:01am

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

htwap · May 9, 2015, 9:31am

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

htwap · May 10, 2015, 6:15pm

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)

thanhmssl10 · May 10, 2015, 6:27pm

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

htwap · May 10, 2015, 6:58pm

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.