Độ phức tạp và Phân tích thuật toán
Phân tích thuật toán định lượng thời gian chạy và bộ nhớ của một thuật toán tăng lên như thế nào theo kích thước đầu vào, cung cấp các công cụ và từ vựng tiệm cận được sử dụng để so sánh các thuật toán và xác định các vấn đề vốn dĩ khó giải quyết.
Definition
Phân tích thuật toán là nghiên cứu về các tài nguyên tính toán — chủ yếu là thời gian và không gian — mà một thuật toán tiêu thụ như một hàm của kích thước đầu vào của nó, cùng với các kỹ thuật được sử dụng để suy ra, biểu diễn và so sánh các giới hạn tài nguyên này.
Scope
Lĩnh vực này bao gồm việc đo lường và so sánh việc sử dụng tài nguyên thuật toán: ký hiệu tiệm cận (big-O, big-Omega, big-Theta), giải các quan hệ đệ quy phát sinh từ các thuật toán đệ quy, phân tích khấu hao của các chuỗi hoạt động, và các kiến thức cơ bản về các lớp độ phức tạp tính toán và NP-đầy đủ khi chúng được áp dụng vào thiết kế thuật toán. Nó đề cập đến chi phí trường hợp xấu nhất, trường hợp trung bình và chi phí khấu hao, cũng như sự phân biệt giữa các vấn đề có thể giải quyết được và không thể giải quyết được. Lý thuyết tính toán rộng hơn (khả năng tính toán, các lớp độ phức tạp hình thức) thuộc về một phân ngành riêng biệt; ở đây trọng tâm là phân tích các thuật toán cụ thể.
Sub-topics
Core questions
- Việc sử dụng tài nguyên của một thuật toán được biểu thị như thế nào một cách độc lập với các chi tiết máy móc và triển khai?
- Phân tích trường hợp xấu nhất, trường hợp trung bình và phân tích khấu hao cho chúng ta biết điều gì?
- Các quan hệ đệ quy được tạo ra bởi các thuật toán đệ quy được giải như thế nào để tìm ra các giới hạn tiệm cận?
- Làm thế nào chúng ta có thể thiết lập các giới hạn dưới cho thấy không có thuật toán nào có thể làm tốt hơn?
- Một vấn đề NP-đầy đủ có nghĩa là gì, và tại sao nó lại quan trọng đối với thiết kế?
Key concepts
- big-O, big-Omega, big-Theta
- phân tích trường hợp xấu nhất và trường hợp trung bình
- quan hệ đệ quy
- định lý Master
- phân tích khấu hao
- giới hạn dưới
- thời gian đa thức
- NP-đầy đủ
Key theories
- Ký hiệu tiệm cận
- Big-O, big-Omega và big-Theta mô tả tốc độ tăng trưởng của việc sử dụng tài nguyên khi kích thước đầu vào tăng lên, trừu tượng hóa các hằng số và các số hạng bậc thấp hơn để cho phép so sánh các thuật toán độc lập với máy móc.
- Khả năng giải quyết và NP-đầy đủ
- Các vấn đề có thể giải quyết được trong thời gian đa thức được coi là có thể giải quyết được; các vấn đề NP-đầy đủ là những vấn đề mà tất cả các vấn đề trong NP đều quy về được, và việc tìm ra một thuật toán đa thức cho bất kỳ vấn đề nào trong số đó sẽ giải quyết được tất cả, một câu hỏi (P so với NP) vẫn còn bỏ ngỏ.
Clinical relevance
Phân tích thuật toán hướng dẫn mọi quyết định kỹ thuật về việc sử dụng thuật toán hoặc cấu trúc dữ liệu nào, dự đoán cách các hệ thống mở rộng khi dữ liệu tăng lên. Việc nhận ra rằng một vấn đề là NP-khó cho các nhà thực hành biết rằng nên tìm kiếm các phương pháp xấp xỉ, heuristic hoặc trường hợp đặc biệt thay vì một thuật toán đa thức chính xác, định hình công việc trong tối ưu hóa, lập lịch và tính toán quy mô lớn.
History
Ký hiệu tiệm cận được đưa vào khoa học máy tính từ lý thuyết số giải tích và được Donald Knuth phổ biến vào những năm 1960 và 1970. Lý thuyết NP-đầy đủ được Stephen Cook (1971) thành lập và được Richard Karp (1972) mở rộng, định hình lại thiết kế thuật toán xung quanh ranh giới giữa các vấn đề có thể giải quyết được và không thể giải quyết được.
Debates
- P so với NP
- Liệu mọi vấn đề mà các giải pháp của nó có thể được xác minh nhanh chóng cũng có thể được giải quyết nhanh chóng (P = NP) là câu hỏi mở trung tâm của khoa học máy tính lý thuyết; người ta thường phỏng đoán rằng P không bằng NP, nhưng chưa có bằng chứng nào tồn tại.
Key figures
- Donald Knuth
- Stephen Cook
- Richard Karp
- Robert Tarjan
Related topics
Seminal works
- cormen2009
- knuth1976bigo
- kleinberg2006
Frequently asked questions
- Sự khác biệt giữa phân tích trường hợp xấu nhất và trường hợp trung bình là gì?
- Phân tích trường hợp xấu nhất giới hạn việc sử dụng tài nguyên trên đầu vào bất lợi nhất của mỗi kích thước, đưa ra một sự đảm bảo. Phân tích trường hợp trung bình ước tính việc sử dụng tài nguyên dự kiến trên một phân phối đầu vào, điều này có thể đại diện hơn cho hiệu suất điển hình nhưng phụ thuộc vào các giả định về phân phối đầu vào.
- Nếu một vấn đề là NP-đầy đủ, liệu có vô vọng để giải quyết nó không?
- Không. NP-đầy đủ có nghĩa là không có thuật toán hiệu quả nào được biết đến cho trường hợp xấu nhất, nhưng các trường hợp cụ thể thường có thể được giải quyết bằng các thuật toán xấp xỉ, heuristic, các thuật toán hàm mũ đủ nhanh trong thực tế, hoặc bằng cách khai thác cấu trúc đặc biệt. Nó báo hiệu một sự thay đổi chiến lược, chứ không phải là không thể.