Đánh giá hiệu suất thuật toán¶

Trong thiết kế thuật toán, chúng ta tuần tự hướng tới hai cấp độ mục tiêu sau.

Tìm ra lời giải cho bài toán: Thuật toán cần tìm ra lời giải chính xác cho bài toán một cách đáng tin cậy trong phạm vi đầu vào quy định.
Tìm kiếm lời giải tối ưu: Một bài toán có thể có nhiều lời giải khác nhau, và chúng ta hy vọng tìm được thuật toán hiệu quả nhất có thể.

Nói cách khác, dưới tiền đề có thể giải quyết được bài toán, hiệu suất thuật toán đã trở thành tiêu chí đánh giá chính để đo lường chất lượng của thuật toán. Nó bao gồm hai khía cạnh sau.

Hiệu suất thời gian: Độ dài thời gian chạy của thuật toán.
Hiệu suất không gian: Dung lượng không gian bộ nhớ mà thuật toán chiếm dụng.

Nói tóm lại, mục tiêu của chúng ta là thiết kế các cấu trúc dữ liệu và thuật toán "vừa nhanh vừa tiết kiệm". Việc đánh giá hiệu suất thuật toán một cách hiệu quả là vô cùng quan trọng, bởi vì chỉ có như vậy chúng ta mới có thể so sánh các thuật toán khác nhau, từ đó định hướng cho quá trình thiết kế và tối ưu hóa thuật toán.

Các phương pháp đánh giá hiệu suất chủ yếu được chia làm hai loại: thử nghiệm thực tế và ước lượng lý thuyết.

Thử nghiệm thực tế¶

Giả sử hiện tại chúng ta có thuật toán A và thuật toán B, cả hai đều có thể giải quyết cùng một bài toán, và bây giờ cần so sánh hiệu suất của hai thuật toán này. Phương pháp trực tiếp nhất là chạy hai thuật toán này trên một máy tính và đo lường thời gian chạy cũng như lượng bộ nhớ sử dụng của chúng. Cách đánh giá này có thể phản ánh đúng thực tế, nhưng cũng tồn tại những hạn chế rất lớn.

Một mặt, rất khó để loại bỏ các yếu tố gây nhiễu từ môi trường thử nghiệm. Cấu hình phần cứng sẽ ảnh hưởng đến hiệu suất của thuật toán. Ví dụ, nếu một thuật toán có mức độ song song cao, nó sẽ phù hợp hơn khi chạy trên CPU đa nhân; nếu một thuật toán thực hiện nhiều thao tác truy xuất bộ nhớ chuyên sâu, nó sẽ hoạt động tốt hơn trên bộ nhớ hiệu năng cao. Nói cách khác, kết quả thử nghiệm của một thuật toán trên các máy khác nhau có thể không đồng nhất. Điều này có nghĩa là chúng ta cần thử nghiệm trên nhiều loại máy và tính toán hiệu suất trung bình, một việc làm không thực tế.

Mặt khác, việc tiến hành thử nghiệm toàn diện vô cùng tốn tài nguyên. Khi lượng dữ liệu đầu vào thay đổi, thuật toán sẽ thể hiện hiệu suất khác nhau. Ví dụ, khi lượng dữ liệu đầu vào nhỏ, thời gian chạy của thuật toán A ngắn hơn so với thuật toán B; nhưng khi lượng dữ liệu đầu vào lớn, kết quả thử nghiệm có thể hoàn toàn ngược lại. Do đó, để đạt được kết luận có sức thuyết phục, chúng ta cần thử nghiệm với dữ liệu đầu vào ở nhiều quy mô khác nhau, điều này đòi hỏi một lượng lớn tài nguyên tính toán.

Ước lượng lý thuyết¶

Vì thử nghiệm thực tế có những hạn chế đáng kể, chúng ta có thể cân nhắc việc đánh giá hiệu suất thuật toán chỉ thông qua các tính toán lý thuyết. Phương pháp ước lượng này được gọi là phân tích độ phức tạp tiệm cận (asymptotic complexity analysis), gọi tắt là phân tích độ phức tạp.

Phân tích độ phức tạp có thể phản ánh mối quan hệ giữa tài nguyên thời gian và không gian cần thiết để thực thi thuật toán với quy mô của dữ liệu đầu vào. Nó mô tả xu hướng tăng của thời gian và không gian cần thiết để thực thi thuật toán khi quy mô dữ liệu đầu vào tăng lên. Định nghĩa này hơi khó hiểu một chút, chúng ta có thể chia nó thành ba điểm mấu chốt sau để hiểu rõ hơn.

“Tài nguyên thời gian và không gian” lần lượt tương ứng với độ phức tạp thời gian (time complexity) và độ phức tạp không gian (space complexity).
“Khi quy mô dữ liệu đầu vào tăng lên” có nghĩa là độ phức tạp phản ánh mối quan hệ giữa hiệu suất chạy của thuật toán và quy mô dữ liệu đầu vào.
“Xu hướng tăng của thời gian và không gian” biểu thị rằng phân tích độ phức tạp không tập trung vào giá trị cụ thể của thời gian chạy hay không gian chiếm dụng, mà tập trung vào tốc độ tăng “nhanh hay chậm” của thời gian hoặc không gian đó.

Phân tích độ phức tạp khắc phục được những nhược điểm của phương pháp thử nghiệm thực tế, thể hiện qua các khía cạnh sau.

Nó không cần thực sự chạy mã nguồn, giúp tiết kiệm năng lượng và thân thiện với môi trường hơn.
Nó độc lập với môi trường thử nghiệm, kết quả phân tích áp dụng được cho mọi nền tảng thực thi.
Nó có thể phản ánh hiệu suất thuật toán ở các lượng dữ liệu khác nhau, đặc biệt là hiệu suất của thuật toán khi lượng dữ liệu lớn.

Tip

Nếu bạn vẫn còn cảm thấy mơ hồ về khái niệm độ phức tạp, đừng lo lắng—chúng ta sẽ tìm hiểu chi tiết về nó trong các chương tiếp theo.

Phân tích độ phức tạp cung cấp cho chúng ta một "thước đo" để đánh giá hiệu suất thuật toán, cho phép đo lường tài nguyên thời gian và không gian cần thiết để thực thi một thuật toán cụ thể, cũng như so sánh hiệu suất giữa các thuật toán khác nhau.

Độ phức tạp là một khái niệm toán học nên có thể khá trừu tượng và có độ khó nhất định đối với người mới bắt đầu. Từ góc độ này, phân tích độ phức tạp có vẻ không phù hợp để giới thiệu ngay từ đầu. Tuy nhiên, khi chúng ta thảo luận về đặc điểm của một cấu trúc dữ liệu hay thuật toán nào đó, việc phân tích tốc độ chạy và tình trạng sử dụng không gian của nó là điều không thể tránh khỏi.

Tóm lại, trước khi đi sâu vào tìm hiểu cấu trúc dữ liệu và thuật toán, khuyến nghị bạn nên xây dựng hiểu biết sơ bộ về phân tích độ phức tạp, từ đó có thể tự thực hiện phân tích độ phức tạp cho các thuật toán đơn giản.