Giới thiệu về Độ phức tạp của thuật toán

Mỗi dòng code khi được thực thi đều phải "trả giá". Cái "giá" này không không hẳn là tiền mà là tài nguyên của máy tính (RAM, CPU, GPU...). Độ phức tạp của thuật toán tương ứng với cái giá mà chúng ta phải trả. Tính toán độ phức tạp của thuật toán đồng nghĩa với việc tính toán cái giá mà chúng ta phải trả.

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

Độ phức tạp của thuật toán (Algorithmic Complexity) là hiểu đơn giản là cách mô tả lượng tài nguyên mà một thuật toán cần để chạy xét theo sự thay đổi của kích thước dữ liệu đầu vào.

Kích thước dữ liệu đầu vào (input size) thường được ký hiệu là n. Đây được coi là yếu tố cốt lõi.

Ví dụ:

• Trong bài toán sắp xếp một mảng, n là số lượng phần tử trong mảng.
• Trong bài toán xử lý chuỗi, n là độ dài chuỗi
• Trong bài toán duyệt đồ thị, n là số đỉnh hoặc số cạnh

Độ phức tạp cho chúng ta biết:" Khi n lớn dần lên, thuật toán của chúng ta sẽ chạy chậm đi hoặc tốn nhiều bộ nhớ hơn theo quy luật nào"

Tại sao cần quan tâm?

Trong môi trường học thuật, thuật toán chỉ cần cho ra kết quả đúng. Nhưng trong thực tế, môi trường product chuyên nghiệp một thuật toán chạy quá chậm hoặc tốn quá nhiều bộ nhớ là một thuật toán vô dụng.

Một thuật toán quá chậm có thể dẫn tới những vấn đề sau:

• Trải nghiệm người dùng tệ hại (thời gian chờ đợi lâu, đơ giật, crash..)
• Chi phí vận hành lớn (yêu cầu quá nhiều RAM, CPU, điện...)
• Khả năng mở rộng (Tốn quá nhiều tài nguyên dẫn đến khó mở rộng)

Độ phức tạp thời gian và Độ phức tạp không gian

Độ phức tạp thời gian (Time complexity)

Độ phức tạp thời gian mô tả thời gian chạy của thuật toán tăng lên như thế nào khi kích thước đầu vào tăng lên

Đây là yếu tố thường được quan tâm nhất. Thời gian ở đây không phải là giây, phút mà là số lượng thao tác cơ bản (gán, so sánh, cộng trừ...) mà máy tính phải thực hiện. Lý do là vì thời gian chạy thực tế còn phụ thuộc vào tốc độ phần cứng, ngôn ngữ lập trình... khi đó số thao tác cần thực hiện được coi là thước đo tuyệt đối.

Độ phức tạp không gian (Space complexity)

Độ phức tạp không gian mô tả lượng bộ nhớ mà một thuật toán cần sử dụng tăng lên như thế nào khi kích thước đầu vào tăng.

Lượng bộ nhớ này bao gồm cả không gian lưu trữ dữ liệu đầu vào và bất kỳ không gian bổ sung nào mà thuật toán cần để hoạt động (VD mảng tạm, biến cục bộ)

Thông thường, có một sự đánh đổi giữa thời gian và không gian. Đôi khi bạn có thể làm cho thuật toán chạy nhanh hơn bằng cách sử dụng nhiều bộ nhớ hơn và ngược lại. Nhiệm vụ của một kỹ sư giỏi là hiểu rõ sự đánh đổi này và chọn giải pháp phù hợp nhất cho bài toán cụ thể.