Cách Tính độ Phức Tạp Của Thuật Toán Fibonacci Và Euclid?

Có thể bạn quan tâm

programmingalgorithm htwap (lu___va_sa__) May 9, 2015, 8:28am #1 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Độ phức tạp: O(((1+sqrt(5))/2)^n)EuclidĐộ phức tạp: O(logarit n cơ số 2)3 Likes Code_Luc_H_ng_Dong (Code Lúc Hừng Đông) May 9, 2015, 8:20am #2 Fibonacci thì có thể tính số fibo thứ n trong O(log n); Còn Euclid thì O(log max(A,B))

2 Likes htwap (lu___va_sa__) May 9, 2015, 8:24am #3 Cách Cách ko hiểu cách tính ạ

1 Like Code_Luc_H_ng_Dong (Code Lúc Hừng Đông) May 9, 2015, 8:25am #4 Lúc nãy em không thấy code của bác

sr bác nhé1 Like Code_Luc_H_ng_Dong (Code Lúc Hừng Đông) May 9, 2015, 8:26am #5 Mà rốt cục bác hỏi là thuật toán hay độ phức tạp

1 Like htwap (lu___va_sa__) May 9, 2015, 8:29am #6

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̣

1 Like Code_Luc_H_ng_Dong (Code Lúc Hừng Đông) May 9, 2015, 8:37am #7 Bác tham khảo cái Euclid ở đây http://vnalgo.com/category/so-hoc/1 Like htwap (lu___va_sa__) May 9, 2015, 8:43am #8 sao trong này cái Euclid lại liên quan Fibonacci vậy ạ?1 Like Code_Luc_H_ng_Dong (Code Lúc Hừng Đông) May 9, 2015, 8:48am #9

Định Lý đả chứng minh

cái này em cũng biết chấp nhận thôi!1 Like htwap (lu___va_sa__) May 9, 2015, 8:57am #10

Đị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

1 Like Code_Luc_H_ng_Dong (Code Lúc Hừng Đông) May 9, 2015, 8:58am #11 Mình đả tận lực :’( Cái này ngoài tầm của em rồi!1 Like htwap (lu___va_sa__) May 9, 2015, 8:59am #12 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̀.

1 Like Rok_Hoang (Minh Hoàng) May 9, 2015, 9:01am #13 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ó. Độ phức tạp thuật toánThờ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à ...2 Likes htwap (lu___va_sa__) May 9, 2015, 9:31am #14

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̣. htwap (lu___va_sa__) May 10, 2015, 6:15pm #15 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)

Fibonacci.png1366×768 53.8 KB 1 Like thanhmssl10 (TP) May 10, 2015, 6:27pm #16 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-toan1 Like htwap (lu___va_sa__) May 10, 2015, 6:58pm #17 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