Đánh giá độ phức tạp của một thuật toán là việc đo lường số lần thực hiện các thao tác cơ bản (như so sánh, gán giá trị, tính toán…) khi xử lý đầu vào có kích thước lớn nhất định. Độ phức tạp của thuật toán thường được đo lường bằng thời gian thực thi hoặc số lần thực hiện các thao tác cơ bản.
Có hai loại độ phức tạp chính: độ phức tạp thời gian và độ phức tạp không gian. Độ phức tạp thời gian đo lường thời gian thực thi của thuật toán, trong khi độ phức tạp không gian đo lượng bộ nhớ cần sử dụng để thực hiện thuật toán.
Đánh giá độ phức tạp của một thuật toán giúp chúng ta hiểu được hiệu quả và tính khả thi của thuật toán khi xử lý các bài toán có kích thước lớn. Nếu độ phức tạp của thuật toán quá cao, chương trình có thể chạy chậm hoặc tốn nhiều bộ nhớ, điều này có thể khiến chương trình không thể xử lý được các bài toán lớn.
Dưới đây là một số độ phức tạp của các thuật toán phổ biến:
- Thuật toán sắp xếp Bubble sort: Độ phức tạp là O(n^2).
- Thuật toán sắp xếp Insertion sort: Độ phức tạp là O(n^2).
- Thuật toán sắp xếp Quick sort: Độ phức tạp là O(nlogn).
- Thuật toán tìm kiếm tuyến tính (Linear search): Độ phức tạp là O(n).
- Thuật toán tìm kiếm nhị phân (Binary search): Độ phức tạp là O(logn).
- Thuật toán Dijkstra (tìm đường đi ngắn nhất): Độ phức tạp là O(ElogV).
- Thuật toán Prim (tìm cây khung nhỏ nhất): Độ phức tạp là O(ElogV).
Lưu ý rằng độ phức tạp của thuật toán có thể khác nhau tùy thuộc vào cách thực hiện cũng như đặc tính của dữ liệu đầu vào. Do đó, khi đánh giá độ phức tạp của một thuật toán, chúng ta cần lưu ý đến các yếu tố này./.