độ phức tạp của thuật toán

độ phức tạp của thuật toán

bác nào có thể giải thích cho em độ phức tạp của thuật toán là gì không ? tính toán nó như thế nào ? em không biết tý gì về cái này, mọi người giải thích cặn kẽ hộ cái nhé

Chào chungtm,
Đấy là một bộ môn nghiên cứu về độ phức tạp của thuật toán, thuộc ngành Computer Science.
Phải kể đến 2 thành phần của độ phức tạp của một thuật toán : thời gian thực hiện và bộ nhớ cần dùng. Độ phức tạp là một hàm trên kích thước đầu vào (dữ liệu) cho kết quả là thời gian (bộ nhớ) tiêu tốn cho quá trình tính toán.
Mặc dù các máy tính hiện nay có tốc độ và kích thước bộ nhớ khác nhau, chúng đều dựa trên một mô hình. Và mọi thuật toán đều được phân rã thành những thao tác cơ bản trên mô hình đấy. Vì thế, để nghiên cứu độ phức tạp, người ta thường dùng mô hình abstrait. Có 2 mô hình tương đương mà người ta hay dùng là Máy Turing, và một Ngôn Ngữ Lập Trình tổng quát.
Mô hình nổi tiếng nhất là Máy Turing, do Turing nghĩ ra : một ô-tô-mát đọc/ghi/dịch chuyển trên một băng ô nhớ. Mỗi thuật toán tương đương với một cài đặt của máy turing. Phải nhắc đến luận đề nổi tiếng Church-Turing : mọi quá trình tính toán cơ học đều có một máy Turing tương ứng. Luận đề này không có chứng minh, nhưng mọi người đều công nhận nó, vì chưa có ngoại lệ nào cả.
Và mô hình lại làm nảy sinh vấn đề mới : có những bài toán không thực hiện được bằng máy Turing - không tính được. Ví dụ là : thuật toán đoán nhận tính dừng của một máy Turing - cho một máy Turing và một dữ liệu, liệu có thể trả lời sau một số bước hữu hạn là máy có dừng không.
Lan man thế, quay lại độ phức tạp, nó sẽ được tính (theo thời gian) là số bước dịch chuyển của máy trên dữ liệu đầu vào hoặc (theo bộ nhớ) số ô nhớ trên băng đã được dùng. Ghi chú thêm là băng nhớ của máy Turing là vô hạn và lúc nãy đến giờ ta chỉ xét về máy đơn định. Cái này sẽ coi là một hàm trên kích thước đầu vào. Nếu đấy là một hàm đa thức, ta gọi đấy là một thuật toán P (polynomial), nếu là hàm mũ thì coi là NP (nondeterminist polynomial) - vì sẽ tương đương P trên máy không đơn định. Các bài toán P mới được coi là hiệu quả, và cũng chỉ với bậc đa thức bé.
Thông thường, độ phức tạp ví dụ thời gian sẽ được tính đại khái bằng số một phép toán cơ bản nào đấy, như cộng, nhân, so sánh.
Thế nhé. Bạn đọc thêm trên mạng, và cũng có nhiều sách về lĩnh vực này đấy.