Quy tắc tính độ phức tạp trên mã nguồn

Các quy tắc nên tảng

Quy tắc bỏ hằng số

Big O chỉ quan tâm đến tốc độ tăng trưởng khi n rất lớn. Do đó, các hệ số hằng số không có ý nghĩa

Ví dụ

• O(2n) → O(n)
• O(500) → O(1)
• O(n/3) → O(n)

Quy tắc lấy thành phần vượt trội

Khi một thuật toán có nhiều thành phần, độ phức tạp tổng thể được quyết định bởi thành phần chậm nhất

Ví dụ

• O(n² + n) → O(n²)
• O(2ⁿ + n²) → O(2ⁿ)
• O(n log n + n log n) → O(n log n)

Các thao tác cơ bản là O(1)

Một thao tác cơ bản không phụ thuộc vào kích thước đầu vào được coi là có độ phức tạp hằng số O(1)

Phân tích mã nguồn

Các câu lệnh tuần tự

public void DoSomething(int[] numbers)
{
    // Phân tích từng dòng:
    Console.WriteLine("Bắt đầu...");             // O(1)

    int sum = numbers[0] + numbers[1];          // O(1)

    for (int i = 0; i < numbers.Length; i++)    // O(n)
    {
        Console.WriteLine(numbers[i]);
    }

    Console.WriteLine("Kết thúc.");              // O(1)
}

Tổng độ phức tạp = O(1) + O(1) + O(n) + O(1) = O(n+3)

Áp dụng quy tắc loại bỏ hằng số và lấy phần vượt trội ta có độ phức tạp là O(n)

Vòng lặp

// n = items.Count
public void LoopExample(List<string> items)
{
    // Vòng lặp này chạy n lần
    foreach (var item in items)
    {
        // Khối lệnh bên trong chỉ có các thao tác O(1)
        Console.WriteLine("Item: " + item); // O(1)
        int length = item.Length;           // O(1)
    }
}

Mỗi vòng lặp tốn O(1) + O(1) = O(1)

Vòng lặp này lặp lại n lần → độ phức tạp là O(n)

Vòng lặp lồng nhau

// n = numbers.Count
public void NestedLoopExample(List<int> numbers)
{
    // Vòng lặp ngoài chạy n lần
    foreach (var num1 in numbers)
    {
        // Vòng lặp trong cũng chạy n lần với mỗi lần lặp của vòng ngoài
        foreach (var num2 in numbers)
        {
            // Thao tác bên trong là O(1)
            Console.WriteLine($"{num1}, {num2}");
        }
    }
}

Độ phức tạp của mỗi vòng lặp trong là O(n)

Vòng lặp trong được lặp lại n lần.

Độ phức tạp của thuật toán là O(n*n) = O(n²)

Câu lệnh điều kiện

public void ConditionalExample(int condition, int[] data)
{
    if (condition == 0)
    {
        // Nhánh này có độ phức tạp O(1)
        Console.WriteLine("Condition is true.");
    }
    else if (condition ==  1)
    {
        // Nhánh này có độ phức tạp O(n)
        foreach (var item in data)
        {
            Console.WriteLine(item);
        }
    } 
    else
    {
        // Nhánh này có độ phức tạp là O(n2)
        foreach (var num1 in numbers)
        {
            foreach (var num2 in numbers)
            {
                Console.WriteLine($"{num1}, {num2}");
            }
        }
    }  
}

Với câu lệnh điều kiện độ phức tạp của thuật toán là độ phức tạp của nhánh tệ nhất.

Trong trường hợp này là O(n²)