Cấu trúc dữ liệu và Giải thuật Bài 6: Tính toán Big-O cho các vòng lặp đơn và vòng lặp lồng nhau.

Sau khi đã nắm vững các khái niệm lý thuyết về Big-O, Best/Worst Case và bài toán Trade-off, đã đến lúc chúng ta áp dụng chúng vào công việc thực tế nhất của một kỹ sư: Đọc mã nguồn và "bắt mạch" hiệu năng.

Kỹ năng tính toán Big-O không đòi hỏi toán học cao siêu. Nó dựa trên việc bạn nhận diện được mô hình của các vòng lặp. Dưới đây là 5 kịch bản kinh điển nhất mà bạn sẽ gặp trong mọi dự án thực tế.

1. Vòng lặp đơn: Thời gian tuyến tính $O(n)$

Đây là mô hình cơ bản nhất. Khối lệnh bên trong vòng lặp sẽ được thực thi đúng $n$ lần (hoặc một tỷ lệ cố định của $n$).

Go

func printItems(n int) {
    for i := 0; i < n; i++ {
        fmt.Println(i) // Phép toán mất O(1)
    }
}

• Phân tích: Vòng lặp chạy từ 0 đến n-1. Lệnh fmt.Println là một thao tác cơ bản mất $O(1)$. Tổng số phép toán là $n \times O(1) = O(n)$.

• Lưu ý bước nhảy: Kể cả khi vòng lặp nhảy cách bước (ví dụ i += 2), nó sẽ thực thi $n/2$ lần. Theo quy tắc bỏ hằng số (Drop Constants), $O(n/2)$ vẫn được rút gọn thành $O(n)$.

2. Hai vòng lặp độc lập liền kề: $O(n + m)$

Một cái bẫy mà người mới học rất hay mắc phải là cứ thấy 2 vòng lặp thì mặc định là $O(n^2)$. Hãy cẩn thận nhìn xem chúng có lồng nhau hay không.

PHP

function processTwoArrays($arrA, $arrB) {
    foreach ($arrA as $item) {
        // Xử lý mảng A (Kích thước n)
    }
    
    foreach ($arrB as $item) {
        // Xử lý mảng B (Kích thước m)
    }
}

• Phân tích: Vòng lặp đầu tiên chạy $n$ lần. Vòng lặp thứ hai chạy $m$ lần. Hai khối này hoàn toàn độc lập, do đó tổng thời gian là $O(n + m)$.

• Quy tắc rút gọn: Bạn không thể rút gọn thành $O(n)$ vì bạn không biết mảng A hay mảng B lớn hơn. Cả hai biến số đều có sức ảnh hưởng đến hiệu năng nên phải giữ lại.

3. Vòng lặp lồng nhau hoàn toàn: Thời gian bậc hai $O(n^2)$

Đây là "kẻ thù" số một gây nghẽn cổ chai (bottleneck) trong các hệ thống xử lý lượng lớn dữ liệu.

Go

func printPairs(n int) {
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            fmt.Println(i, j)
        }
    }
}

• Phân tích: Cứ mỗi một lần biến i chạy, biến j sẽ chạy đủ $n$ vòng. Với $n$ lần của i, tổng số thao tác in ra màn hình sẽ là $n \times n = n^2$.

• Kết luận: Độ phức tạp là $O(n^2)$. Nếu có 3 vòng lặp lồng nhau duyệt qua $n$, độ phức tạp sẽ là $O(n^3)$.

4. Vòng lặp lồng nhau phụ thuộc (Tam giác): Vẫn là $O(n^2)$

Kịch bản này tinh vi hơn và thường xuất hiện trong các thuật toán như Sắp xếp chọn (Selection Sort) hoặc duyệt các cặp phần tử không lặp lại.

Go

func printUniquePairs(n int) {
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ { // Lưu ý: j bắt đầu từ i + 1
            fmt.Println(i, j)
        }
    }
}

• Phân tích:

  • Khi i = 0, vòng lặp j chạy $n-1$ lần.

  • Khi i = 1, vòng lặp j chạy $n-2$ lần.

  • ...

  • Khi i = n-2, vòng lặp j chạy $1$ lần.

• Toán học đằng sau: Tổng số phép toán là cấp số cộng: $(n-1) + (n-2) + ... + 2 + 1 = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}$.

• Kết luận: Áp dụng quy tắc loại bỏ hằng số ($\frac{1}{2}$) và loại bỏ hạng tử bậc thấp ($n$), kết quả cuối cùng vẫn được xếp vào nhóm $O(n^2)$.

5. Vòng lặp nhảy bước theo cấp số nhân: $O(\log n)$

Nếu bước nhảy không phải là phép cộng (+ 1, + 2) mà là phép nhân hoặc chia, thời gian chạy sẽ giảm xuống cực kỳ khủng khiếp.

PHP

function logarithmicLoop($n) {
    for ($i = 1; $i < $n; $i = $i * 2) {
        echo $i;
    }
}

• Phân tích: Thay vì tăng từng đơn vị, i tăng vọt: 1, 2, 4, 8, 16, 32...

• Toán học đằng sau: Vòng lặp sẽ dừng lại khi $2^k = n$ (với $k$ là số bước lặp). Lấy logarit cơ số 2 hai vế, ta có $k = \log_2 n$.

• Kết luận: Độ phức tạp là $O(\log n)$. Nếu $n = 1,000,000$, vòng lặp này chỉ chạy đúng 20 lần. Đây là dấu hiệu nhận biết của các thuật toán cực kỳ tối ưu như Tìm kiếm nhị phân (Binary Search).

Khả năng nhìn code và "nhẩm" ra Big-O là ranh giới giữa một lập trình viên viết code theo bản năng và một kỹ sư làm chủ được hệ thống của mình. Khi bạn review một đoạn mã (Pull Request) chứa vòng lặp lồng nhau truy vấn vào Database, bộ não bạn giờ đây sẽ tự động bật cảnh báo $O(n^2)$ để yêu cầu tối ưu trước khi gộp (merge) code.

Tuy nhiên, đánh giá thuật toán không chỉ có vòng lặp. Sự rẽ nhánh trong logic cũng đóng vai trò then chốt. Ở bài tiếp theo, chúng ta sẽ xem xét cách xử lý Big-O khi mã nguồn chứa hàng loạt các câu lệnh if/else và các lời gọi hàm lồng nhau.