Độ phức tạp thuật toán là gì?

Độ phức tạp của thuật toán, (độ phức tạp tính toán hoặc độ phức tạp của Kolmogorov), là một ý tưởng nền tảng trong cả lý thuyết phức tạp tính toán

và lý thuyết thông tin thuật toán, và đóng vai trò quan trọng trong cảm ứng chính thức.Độ phức tạp thuật toán của chuỗi nhị phân được định nghĩa là chương trình ngắn nhất và hiệu quả nhất có thể tạo ra chuỗi.Mặc dù có vô số chương trình có thể tạo ra bất kỳ chuỗi nào, một chương trình hoặc nhóm chương trình sẽ luôn là ngắn nhất.Không có cách nào để tìm thuật toán ngắn nhất xuất ra một chuỗi đã cho;Đây là một trong những kết quả đầu tiên của lý thuyết phức tạp tính toán.Mặc dù vậy, chúng ta có thể đưa ra một phỏng đoán có học thức.Kết quả này, (độ phức tạp tính toán của một chuỗi), hóa ra rất quan trọng đối với các bằng chứng liên quan đến khả năng tính toán. Vì bất kỳ đối tượng hoặc thuộc tính vật lý nào về nguyên tắc có thể được mô tả để kiểm tra gần như một chuỗi các bit, đối tượng và thuộc tínhCó thể nói là có độ phức tạp thuật toán là tốt.Trên thực tế, việc giảm sự phức tạp của các đối tượng trong thế giới thực cho các chương trình tạo ra các đối tượng làm đầu ra, là một cách để xem doanh nghiệp khoa học.Các đối tượng phức tạp xung quanh chúng ta có xu hướng đến từ ba quá trình tạo chính;Sự xuất hiện , Sự tiến hóa và trí thông minh , với các đối tượng được tạo ra bởi mỗi xu hướng đối với độ phức tạp thuật toán lớn hơn.của các vấn đề toán học và logic.Hơn 400 lớp phức tạp tồn tại và các lớp bổ sung liên tục được phát hiện.Câu hỏi nổi tiếng p ' np

liên quan đến bản chất của hai trong số các lớp phức tạp này.Các lớp học phức tạp bao gồm các vấn đề khó khăn hơn nhiều so với bất cứ điều gì người ta có thể đối mặt trong toán học cho đến tính toán.Có nhiều vấn đề có thể tưởng tượng được trong lý thuyết phức tạp tính toán sẽ đòi hỏi một lượng thời gian gần như vô hạn để giải quyết. Độ phức tạp thuật toán và các khái niệm liên quan đã được phát triển vào những năm 1960 bởi hàng chục nhà nghiên cứu.Andrey Kolmogorov, Ray Solomonoff và Gregory Chaitin đã có những đóng góp quan trọng vào cuối những năm 60 với lý thuyết thông tin thuật toán.Nguyên tắc về độ dài tin nhắn tối thiểu, liên quan chặt chẽ đến độ phức tạp của thuật toán, cung cấp nhiều nền tảng của suy luận thống kê và cảm ứng và học máy.