Khi lựa chọn một hàm để áp dụng vào công tác phát triển phần mềm, chúng ta thường ưu tiên lựa chọn các thuật toán có hiệu suất tốt. Ngoài ra, phương pháp đo hiệu suất còn cho ra chỉ số quan trọng để chúng ta quyết định chúng ta có cần tối ưu lại thuật toán hay không.
Khi nói đến đo hiệu suất thuật thuật toán, chúng ta cần làm quen với thuật ngữ Big O notation, với ngữ nghĩa là biểu thị độ phức tạp về thời gian thực thi (time complexity) của thuật toán đó khi đầu vào tăng lên và xử lý khối lượng công việc lớn.
Ý nghĩa của các công thức Big O notation
1. O(1) (Thời gian hằng)
Thuật toán có độ phức tạp thời gian O(1) luôn thực hiện trong một khoảng thời gian cố định, không phụ thuộc vào kích thước đầu vào n. Dù đầu vào lớn hay nhỏ, thuật toán luôn chạy trong một khoảng thời gian cố định.
Ví dụ: Khi truy cập một phần tử trong mảng theo vị trí (index) array[i], thuật toán luôn thực hiện trong một khoảng thời gian cố định. Đây là độ phức tạp thời gian nhanh nhất vì thời gian thực hiện không thay đổi khi kích thước đầu vào thay đổi.
2. O(log n) (Thời gian logarit)
Thời gian thực hiện của thuật toán tăng theo logarit của kích thước đầu vào n. Thuật toán này chia nhỏ không gian tìm kiếm một cách liên tục, ví dụ: chia đôi ở mỗi bước. Ví dụ khi n tăng lên gấp đôi, giá trị log2(n) chỉ tăng thêm 1 đơn vị (từ 20 lên 21).
Các thuật toán đạt hiệu suất O(log n) sẽ tốt hơn cho các bài toán tìm kiếm trong các cấu trúc dữ liệu đã được sắp xếp (như mảng đã sắp xếp hoặc cây tìm kiếm nhị phân). Các thuật toán phân chia và chinh phục (divide and conquer) thường có độ phức tạp O(log n). Rất hiệu quả với dữ liệu lớn, vì thời gian thực hiện tăng rất chậm ngay cả khi kích thước đầu vào tăng lớn.
3. O(n) (Thời gian tuyến tính)
Một thuật toán có độ phức tạp thời gian là O(n) có nghĩa là thời gian thực hiện tăng tuyến tính (tỷ lệ thuận) theo logarit của kích thước đầu vào n. Khi kích thước đầu vào tăng gấp đôi, thời gian thực thi cũng tăng gấp đôi (log base 2), nhưng điều này không ảnh hưởng nhiều đến sự khác biệt tổng quát về hiệu suất.
Độ phức tạp O(log n), thời gian thực thi tăng tỉ lệ thuận với kích thước đầu vào tăng bởi vì như ví dụ nó duyệt qua toàn bộ một mảng một lần.
4. O(n log n) (Thời gian tuyến tính-logarit)
- Ý nghĩa: Thời gian thực thi là tích của kích thước đầu vào và logarit của kích thước đầu vào.
- Ví dụ: Các thuật toán sắp xếp hiệu quả như Merge Sort, Quick Sort.
5. O(n²) (Thời gian bình phương)
- Ý nghĩa: Thời gian thực thi tăng theo bình phương của kích thước đầu vào. Khi kích thước đầu vào tăng gấp đôi, thời gian thực thi tăng gấp bốn lần.
- Ví dụ: Sắp xếp chọn (Selection Sort), sắp xếp bọt (Bubble Sort).
6. O(n!) (Thời gian giai thừa)
- Ý nghĩa: Thời gian thực thi tăng theo giai thừa của kích thước đầu vào. Đây là một độ phức tạp rất lớn và thường không mong muốn trong các thuật toán thực tế.
- Ví dụ: Giải bài toán du lịch hàng (Traveling Salesman Problem) bằng cách liệt kê tất cả các khả năng.
Bảng so sánh các hiệu suất Big O notation
|
Big O notation |
Đánh giá |
| O(1) | Thời gian hằng số - Nhanh nhất, không phụ thuộc vào kích thước đầu vào. |
| O(log n) | Thời gian logarit - Rất hiệu quả, đặc biệt với tập dữ liệu lớn. |
| O(n) | Thời gian tuyến tính - Tốt với tập dữ liệu nhỏ đến vừa, tăng nhanh với kích thước lớn. |
| O(n log n) | Thời gian tuyến tính-logarit - Hiệu quả nhất cho các thuật toán sắp xếp tối ưu. |
| O(n²) | Thời gian bậc hai - Chỉ hiệu quả với tập dữ liệu nhỏ. |
| O(n!) | Thời gian giai thừa - Không hiệu quả với tập dữ liệu lớn, chỉ phù hợp với các bài toán rất nhỏ. |
