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ạ… :smiley:

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)

3 Likes

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

2 Likes

Cách Cách ko hiểu cách tính ạ :cry:

1 Like

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

1 Like

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

1 Like

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õ ạ :cry:

1 Like

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

1 Like

sao trong này cái Euclid lại liên quan Fibonacci vậy ạ?

1 Like

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

1 Like

:joy: e cần hiểu để thuyết trình :cry:

1 Like

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

1 Like

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ì. :cry:

1 Like

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

2 Likes

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)

1 Like

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 :blush:

https://sites.google.com/site/quanghd/home/danh
http://tek.eten.vn/danh-gia-do-phuc-tap-thuat-toan

1 Like

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.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?