# 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<sup><span class="editor-theme-superscript">2</span></sup><span style="white-space: pre-wrap;"> + n) → O(n</span><sup><span class="editor-theme-superscript">2</span></sup>)
- O(2<sup><span class="editor-theme-superscript">n</span></sup><span style="white-space: pre-wrap;"> + n</span><sup><span class="editor-theme-superscript">2</span></sup>) → O(2<sup><span class="editor-theme-superscript">n</span></sup>)
- 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ự

```c#
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

```c#
// 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

```c#
// 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<sup><span class="editor-theme-superscript">2</span></sup>)

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

```c#
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<sup><span class="editor-theme-superscript">2</span></sup>)