Độ phức tạp của thuật toán (biểu diễn bằng Big-O Notation), là một biểu thức mô tả hành vi thuật toán (ví dụ, về mặt thời gian tính toán hoặc lượng bộ nhớ cần dùng) khi kích thước dữ liệu thay đổi.

Nói đơn giản nó dùng để đánh giá một thuật toán.

• Với các thuật toán có độ phức tạp là O(n), khi dữ liệu đầu vào có 10 phần tử, chương trình phải chạy 10 operation. Khi số dữ liệu đầu vào tăng gấp đôi, số lượng câu lệnh phải tăng gấp đôi
• Nếu độ phức tạp là O(n²), khi số lượng dữ liệu đầu vào tăng gấp đôi, số lượng câu lệnh phải tăng gấp 2² tức là gấp 4 lần
• Nói túm lại, thuật toán có độ phức tạp càng lớn, khi số lượng dữ liệu càng nhiều hơn lên thì nó sẽ chạy càng chậm.

Phân biệt time và space complexity

• Time Complexity: Số lượng câu lệnh phải chạy – thời gian chạy của thuật toán dựa theo lượng phần tử đầu vào.
• Space Complexity: Số lượng bộ nhớ thêm mà thuật toán cần, dựa theo số lượng phần tử đầu vào.

Hay hiểu đơn giản là:

• Time Complexity: Thời gian chương trình cần để hoàn thành công việc.
• Space Complexity: Lượng bộ nhớ chương trình cần để thực hiện công việc.

Ví dụ đơn giản

Giả sử bạn có một danh sách các số và muốn tìm số lớn nhất.

• Cách 1: Bạn duyệt qua từng số và so sánh với số lớn nhất hiện tại. Nếu tìm thấy số lớn hơn, bạn cập nhật số lớn nhất. Cách này có Time Complexity tỷ lệ thuận với số lượng số trong danh sách (n).
• Cách 2: Bạn sắp xếp danh sách theo thứ tự giảm dần, sau đó lấy số đầu tiên. Cách này có Time Complexity cao hơn vì cần sắp xếp danh sách.

Dân dã gần gũi non-tech hơn:

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

Hãy tưởng tượng bạn là một đầu bếp và đang chuẩn bị bữa tối cho một nhóm khách. Số lượng khách càng nhiều, thời gian bạn cần để nấu ăn càng lâu. Ví dụ:

• 1 khách: Bạn chỉ cần nấu một suất ăn, có thể mất 30 phút.