DAA - Phân tích các thuật toán
Trong phân tích lý thuyết các thuật toán, người ta thường ước lượng độ phức tạp của chúng theo nghĩa tiệm cận, tức là ước tính hàm phức tạp cho đầu vào lớn tùy ý. Thời hạn"analysis of algorithms" được đặt ra bởi Donald Knuth.
Phân tích thuật toán là một phần quan trọng của lý thuyết độ phức tạp tính toán, lý thuyết này cung cấp ước tính lý thuyết cho các tài nguyên cần thiết của một thuật toán để giải quyết một vấn đề tính toán cụ thể. Hầu hết các thuật toán được thiết kế để làm việc với các đầu vào có độ dài tùy ý. Phân tích các thuật toán là việc xác định lượng tài nguyên thời gian và không gian cần thiết để thực thi nó.
Thông thường, hiệu quả hoặc thời gian chạy của một thuật toán được nêu dưới dạng một hàm liên quan đến độ dài đầu vào với số bước, được gọi là time complexityhoặc khối lượng bộ nhớ, được gọi là space complexity.
Nhu cầu phân tích
Trong chương này, chúng ta sẽ thảo luận về nhu cầu phân tích các thuật toán và cách chọn một thuật toán tốt hơn cho một bài toán cụ thể vì một bài toán tính toán có thể được giải bằng các thuật toán khác nhau.
Bằng cách xem xét một thuật toán cho một vấn đề cụ thể, chúng ta có thể bắt đầu phát triển tính năng nhận dạng mẫu để các loại vấn đề tương tự có thể được giải quyết nhờ sự trợ giúp của thuật toán này.
Các thuật toán thường khá khác biệt với nhau, mặc dù mục tiêu của các thuật toán này là giống nhau. Ví dụ, chúng ta biết rằng một tập hợp các số có thể được sắp xếp bằng các thuật toán khác nhau. Số lượng phép so sánh được thực hiện bởi một thuật toán có thể thay đổi với những thuật toán khác cho cùng một đầu vào. Do đó, độ phức tạp về thời gian của các thuật toán đó có thể khác nhau. Đồng thời, chúng ta cần tính toán không gian bộ nhớ theo yêu cầu của từng thuật toán.
Phân tích thuật toán là quá trình phân tích khả năng giải quyết vấn đề của thuật toán về thời gian và kích thước cần thiết (dung lượng bộ nhớ để lưu trữ trong khi thực hiện). Tuy nhiên, mối quan tâm chính của việc phân tích các thuật toán là thời gian hoặc hiệu suất cần thiết. Nói chung, chúng tôi thực hiện các loại phân tích sau:
Worst-case - Số bước tối đa được thực hiện trên mọi trường hợp có kích thước a.
Best-case - Số bước tối thiểu được thực hiện trên bất kỳ trường hợp nào có kích thước a.
Average case - Số bước trung bình được thực hiện trên bất kỳ trường hợp nào có kích thước a.
Amortized - Một chuỗi các hoạt động được áp dụng cho đầu vào của kích thước a tính trung bình theo thời gian.
Để giải quyết một vấn đề, chúng ta cần xem xét độ phức tạp về thời gian cũng như không gian vì chương trình có thể chạy trên một hệ thống mà bộ nhớ có hạn nhưng có đủ dung lượng hoặc có thể ngược lại. Trong bối cảnh này, nếu chúng ta so sánhbubble sort và merge sort. Sắp xếp bong bóng không yêu cầu bộ nhớ bổ sung, nhưng sắp xếp hợp nhất yêu cầu thêm không gian. Mặc dù độ phức tạp về thời gian của sắp xếp bong bóng cao hơn so với sắp xếp hợp nhất, chúng ta có thể cần áp dụng sắp xếp bong bóng nếu chương trình cần chạy trong một môi trường có bộ nhớ rất hạn chế.