Cấu trúc dữ liệu và Giải thuật Bài 7: Đánh giá độ phức tạp của các lệnh rẽ nhánh và gọi hàm.

Trong các dự án thực tế, mã nguồn của chúng ta hiếm khi chỉ chạy một mạch từ trên xuống dưới qua vài vòng lặp. Để đáp ứng các nghiệp vụ phức tạp, code sẽ luôn chứa những ngã rẽ if/else, lệnh switch, và hàng tá lời gọi đến các hàm phụ trợ (helper functions).

Việc tính toán Big-O sẽ trở nên thiếu chính xác nếu bạn bỏ qua chi phí tiềm ẩn đằng sau những câu lệnh điều kiện và lời gọi hàm này. Dưới đây là các nguyên tắc cốt lõi giúp bạn đánh giá toàn diện.

1. Lệnh rẽ nhánh (If/Else): Quy tắc "Kẻ tồi tệ nhất"

Khi mã nguồn có nhiều nhánh thực thi khác nhau, chúng ta không cộng dồn độ phức tạp của các nhánh lại. Nhớ lại nguyên lý của Big-O: Chúng ta luôn đánh giá hệ thống ở Trường hợp xấu nhất (Worst Case).

Do đó, độ phức tạp của toàn bộ khối if/else sẽ bằng nhánh có độ phức tạp lớn nhất.

PHP

function processData($arr) {
    if (count($arr) < 10) {
        // Nhánh 1: Mất O(1)
        return $arr[0];
    } else {
        // Nhánh 2: Mất O(n)
        $sum = 0;
        foreach ($arr as $item) {
            $sum += $item;
        }
        return $sum;
    }
}

• Phân tích: Nhánh if thực thi trong thời gian $O(1)$. Nhánh else thực thi trong thời gian $O(n)$ với $n$ là kích thước mảng.

• Kết luận: Dù dữ liệu đầu vào đôi khi nhỏ hơn 10 phần tử, ta vẫn phải kết luận độ phức tạp của hàm processData là $O(n)$ để đảm bảo khả năng chịu tải cao nhất.

2. Gọi hàm tuần tự: Quy tắc "Kẻ thống trị"

Khi bạn gọi nhiều hàm liên tiếp nhau trong một khối lệnh, tổng thời gian sẽ bằng tổng thời gian của từng hàm cộng lại. Tuy nhiên, theo quy tắc loại bỏ hạng tử bậc thấp (Drop Non-Dominant Terms), hàm nào "chậm nhất" sẽ quyết định Big-O của cả khối.

Go

func handleRequest(data []int) {
    validateData(data)  // Giả sử hàm này tốn O(1)
    sortData(data)      // Giả sử dùng Quick Sort tốn O(n log n)
    printData(data)     // Duyệt qua mảng tốn O(n)
}

• Phân tích: Tổng thời gian là $O(1) + O(n \log n) + O(n)$.

• Kết luận: Hạng tử $O(n \log n)$ là lớn nhất và chi phối toàn bộ hàm. Các thành phần $O(1)$ và $O(n)$ bị lược bỏ. Độ phức tạp cuối cùng của handleRequest là $O(n \log n)$.

3. "Sát thủ tàng hình": Lời gọi hàm bên trong vòng lặp

Đây là nguyên nhân phổ biến nhất gây sập server của các lập trình viên thiếu kinh nghiệm. Một vòng lặp trông có vẻ rất vô hại ($O(n)$), nhưng bên trong nó lại gọi một hàm khác. Nếu bạn không nắm rõ hàm bên trong đang làm gì, bạn rất dễ tạo ra "bom nổ chậm".

PHP

function containsValue($arr, $target) {
    // Hàm này dùng Linear Search, tốn O(m) với m là số lượng phần tử
    foreach ($arr as $val) {
        if ($val === $target) return true;
    }
    return false;
}

function processMultipleArrays($mainArray, $targetArray) {
    // Vòng lặp này duyệt qua n phần tử của mainArray -> tốn O(n)
    foreach ($mainArray as $item) {
        // GỌI HÀM BÊN TRONG VÒNG LẶP
        if (containsValue($targetArray, $item)) {
            echo "Found!";
        }
    }
}

• Phân tích: Vòng lặp ngoài cùng chạy $n$ lần. Trong mỗi lần lặp, hệ thống lại nhảy vào hàm containsValue và chạy thêm $m$ lần nữa (với $m$ là kích thước của $targetArray).

• Toán học đằng sau: Đây thực chất chính là hai vòng lặp lồng nhau được ngụy trang dưới dạng lời gọi hàm. Số phép toán là $n \times m$.

• Kết luận: Độ phức tạp là $O(n \times m)$. Nếu cả hai mảng đều lớn, đây là một thuật toán cực kỳ tốn kém.

Liên hệ thực tế (N+1 Query Problem): Nếu bạn từng làm việc với ORM trong Laravel (Eloquent) hay Go (GORM), lỗi N+1 Query kinh điển cũng hoạt động theo cơ chế này. Bạn dùng vòng lặp để duyệt $n$ bài viết (bước 1), trong mỗi vòng lặp lại gọi hàm lấy thông tin tác giả (bước 2 - thực thi 1 câu query SQL tốn kém). Kết quả là Database bị dội bom bằng $N+1$ câu truy vấn, làm nghẽn toàn bộ hệ thống.

4. Hàm đệ quy (Recursive Calls)

Đánh giá độ phức tạp của đệ quy là một chương riêng biệt và khó nhằn hơn. Một hàm gọi lại chính nó không đơn thuần là vòng lặp. Để tính Time Complexity cho đệ quy, ta phải tính số lần hàm được gọi nhân với độ phức tạp của mỗi lần gọi.

• Ví dụ: Hàm đệ quy tính Giai thừa ($n!$) có độ phức tạp là $O(n)$ vì nó gọi lại chính nó $n$ lần.

• Tuy nhiên, hàm đệ quy tính dãy Fibonacci kinh điển lại phân nhánh thành cây, tạo ra số lời gọi hàm khổng lồ, khiến độ phức tạp chạm mức thảm họa $O(2^n)$. (Chúng ta sẽ đi sâu vào vấn đề này ở Chương 8).

Vậy là chúng ta đã nắm trong tay toàn bộ công cụ để phân tích Big-O từ lý thuyết đến mã nguồn thực tế. Tuy nhiên, có một trường hợp đặc biệt: một thuật toán phần lớn thời gian chạy cực kỳ nhanh ($O(1)$), nhưng thỉnh thoảng lại bất ngờ chạy chậm rề rề ($O(n)$). Đánh giá nó là $O(n)$ thì quá oan uổng, mà $O(1)$ thì lại thiếu chính xác.

Đó là lúc chúng ta cần đến một phương pháp đánh giá "công bằng" hơn trong bài học tiếp theo: Amortized Analysis (Phân tích khấu hao).