Cho mình hỏi bạn nào biết cách tính độ phức tạp của các thuật toán có thể giải thích ngắn gọn cho mình cách tính hoặc có tài liệu nào dễ hiểu chút cho mình xin để tìm hiểu. Kỳ này mình học môn Trí Tuệ Nhân Tạo có liên quan khá nhiều đến thuật toán mà lại không biết gì về cách tính độ phức tạp thuật toán. Mình cảm ơn.
Cách tính độ phức tạp của thuật toán?
2 Likes
Mình cũng hóng 
Hồi trước làm mấy đề thi hsg có ghi độ phức tạp mà mình không hiểu lắm
1 Like
P/s: Vẫn biết là đào mộ, nhưng mình vẫn cmt.
6 Likes
ví dụ đơn giản:
int n = b + c;
Có độ phức tạp là O(1)
int n = b + c; // Độ phức tạp là 1
for(int index = 0; index < n; index++)
{
}
có độ phức tạp là 1 + n => O(n) vì 1 quá nhỏ nên bỏ qua
int n = b + c;
for(int index = 0; index < n; index++)
{
for(;n;)
}
Có độ phức tạp là 1 + n mũ 2 ==> O(n mũ 2)
Còn mấy cái phức tạp như O(log(n)) thì lên mạng search sẽ có chỉ cách tính =))
3 Likes
Khi tính phải cẩn trọng với độ phức tạp của các câu lệnh thành phần. Ngoài ra nếu có break; thì chuyện nó không đơn giản đâu.
3 Likes
Cách tính độ phức tập của thuật toán có 2 dạng. Hồi mới học mình cũng loay hoay phân vân khó hiểu.
1 là tính độ phức táp trên code đã có sắn hoặc đã có giả mã. ( thường lập trình viên làm cách này. Nghĩ ra thuật toán thì code r mới đánh giá)
2 là tính độ phức tạp khi chưa có giải mã hay code. Mà tính khi mới hình thành ý tưởng, khi phân tích trên cơ sở toán học. Cái này kiến thức toán phải vững (thường mấy người học chuyên toán hoặc khmt. Theo hướng nghiên cứu. Phân tích thiết kế thuật toán hay làm cách này)
4 Likes
Mình thấy bài viết này hướng dẫn cách tính BigO rất thực tế (xem như dựa trên mã giả) với 4 quy tắc khi tính BigO:
- Quy tắc bỏ hằng số
- Quy tắc lấy max
- Quy tắc cộng
- Quy tắc nhân
Cũng như link đến ví dụ 8 độ phức tạp của vài thuật toán cơ bản.
5 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?