Phân tích độ phức tạp thuật toán (Big O Notation): Những cạm bẫy khi tính thời gian chạy

Big O không chỉ là đếm số vòng lặp for#

Nhiều lập trình viên có thói quen tính độ phức tạp thuật toán rất ngây thơ: Thấy 1 vòng lặp for thì kết luận là $O(N)$, thấy 2 vòng lặp for lồng nhau thì kết luận là $O(N^2)$.

Thực tế, có rất nhiều cạm bẫy tiềm ẩn bên trong các phương thức có sẵn của ngôn ngữ khiến độ phức tạp thực tế nặng hơn bạn tưởng gấp nhiều lần.

3 Cạm bẫy Big O kinh điển cần tránh#

Cạm bẫy 1: Gọi hàm tốn $O(N)$ bên trong vòng lặp $O(N)$#

// ĐOẠN CODE NÀY LÀ O(N^2), KHÔNG PHẢI O(N)!
for (let i = 0; i < array.length; i++) {
  if (array.includes(target[i])) { // Hàm includes() tự nó là một vòng lặp O(N)!
    // do something
  }
}

• Khắc phục: Chuyển mảng sang cấu trúc Set trước vòng lặp để hàm set.has() chỉ tốn $O(1)$ $\rightarrow$ Tổng độ phức tạp giảm xuống $O(N)$!

Cạm bẫy 2: Nối chuỗi (String Concatenation) trong vòng lặp#

Trong các ngôn ngữ mà String là bất biến (Immutable như Java, JavaScript, Python):

String s = "";
for (int i = 0; i < n; i++) {
    s += i; // Mỗi lần cộng chuỗi là tạo một object mới và copy toàn bộ chuỗi cũ!
}

Đoạn code trên có độ phức tạp là $O(N^2)$! Hãy luôn sử dụng StringBuilder trong Java hoặc mảng join() để đạt $O(N)$.

Cạm bẫy 3: Coi thường hằng số lớn (Large Constant Factor)#

Về mặt lý thuyết Big O, thuật toán $O(N)$ tốt hơn $O(N \log N)$. Nhưng nếu thuật toán $O(N)$ có hệ số ẩn là $1000N$, còn $O(N \log N)$ chỉ là $2N \log N$, thì với $N < 1.000.000$, thuật toán $O(N \log N)$ thực tế lại chạy nhanh hơn nhiều!

Bảng tra cứu độ phức tạp các cấu trúc dữ liệu thông dụng#

Góc thảo luận#

Bạn đã từng tối ưu một đoạn code từ $O(N^2)$ xuống $O(N)$ giúp giảm thời gian chạy từ vài chục phút xuống vài giây chưa?

Xem thêm nội dung liên quan:

• Bộ 2.916 câu trắc nghiệm Thuật toán
• Lộ trình Khoa học Máy tính Căn bản