Cẩm nang Big-O: Thước đo hiệu năng thuật toán trong C#

1. O(1) - Constant Time (Thời gian hằng số)

Dù dữ liệu có lớn đến đâu, máy tính cũng chỉ thực hiện đúng một hoặc một số bước cố định.

Đặc điểm: Không có vòng lặp phụ thuộc vào biến đầu vào n.
Mã nguồn C#:

// n là độ dài của mảng
public void GetFirstElement(int[] arr) 
{
    if (arr.Length > 0) 
    {
        int result = arr[0]; // Chỉ 1 bước truy cập duy nhất
        Console.WriteLine(result);
    }
}

2. O(log n) - Logarithmic Time (Thời gian Lôgarit)

Mỗi bước thực hiện, thuật toán sẽ loại bỏ được một nửa số lượng phần tử cần xử lý.

Đặc điểm: Thường thấy trong các vòng lặp mà biến điều khiển được nhân hoặc chia đôi sau mỗi lần lặp.
Mã nguồn C# (Thuật toán tìm kiếm nhị phân thuần):

public int BinarySearch(int[] sortedArr, int target) 
{
    int left = 0;
    int right = sortedArr.Length - 1;

    while (left <= right) 
    {
        int mid = left + (right - left) / 2; // Tìm điểm giữa
        if (sortedArr[mid] == target) return mid;
        
        if (sortedArr[mid] < target) left = mid + 1; // Bỏ nửa trái
        else right = mid - 1; // Bỏ nửa phải
    }
    return -1;
}

3. O(n) - Linear Time (Thời gian tuyến tính)

Thời gian chạy tỷ lệ thuận 1:1 với kích thước dữ liệu.

Đặc điểm: Một vòng lặp duy nhất chạy từ 0 đến n.
Mã nguồn C# (Tìm kiếm tuần tự):

public bool IsValueExists(int[] arr, int target) 
{
    for (int i = 0; i < arr.Length; i++) // Chạy n lần
    {
        if (arr[i] == target) return true;
    }
    return false;
}

4. O(n log n) - Linearithmic Time

Đây là sự kết hợp giữa việc duyệt qua từng phần tử (n) và chia để trị (log n).

Đặc điểm: Thường là các thuật toán sắp xếp nhanh.
Mã nguồn C# (Minh họa thuật toán Merge Sort - chia nhỏ rồi gộp):

// Logic rút gọn của Merge Sort: 
// 1. Chia đôi mảng cho đến khi còn 1 phần tử (log n)
// 2. Trộn các mảng lại với nhau bằng cách duyệt qua chúng (n)
public void MergeSort(int[] arr) 
{
    // Cần hàm đệ quy để chia và một vòng lặp để gộp
    // Kết quả là n * log n
}

5. O(n^2) - Quadratic Time (Thời gian bình phương)

Thời gian chạy tăng theo bình phương của n. Rất chậm với dữ liệu lớn.

Đặc điểm: Hai vòng lặp lồng nhau.
Mã nguồn C# (Thuật toán sắp xếp nổi bọt - Bubble Sort):

public void BubbleSort(int[] arr) 
{
    int n = arr.Length;
    for (int i = 0; i < n; i++)               // Vòng lặp 1
    {
        for (int j = 0; j < n - i - 1; j++)   // Vòng lặp 2 lồng bên trong
        {
            if (arr[j] > arr[j + 1]) 
            {
                // Hoán vị (Swap)
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

6. O(2^n) - Exponential Time (Thời gian hàm mũ)

Mỗi khi dữ liệu tăng thêm 1 đơn vị, thời gian chạy sẽ gấp đôi.

Đặc điểm: Đệ quy gọi lại chính nó 2 lần trong một hàm.
Mã nguồn C# (Tính số Fibonacci không tối ưu):

public int Fibonacci(int n) 
{
    if (n <= 1) return n;
    // Mỗi lời gọi hàm lại sinh ra 2 lời gọi hàm mới -> Tăng trưởng theo cấp số nhân
    return Fibonacci(n - 1) + Fibonacci(n - 2); 
}

Tổng kết và lời khuyên:

Hạn chế O(n^2): Nếu bạn thấy code có 2 vòng for lồng nhau trên cùng một tập dữ liệu lớn, hãy tìm cách dùng Dictionary (bảng băm) để đưa về $O(n)$.
Tận dụng O(log n): Luôn sắp xếp dữ liệu trước nếu bạn phải tìm kiếm nhiều lần trên tập dữ liệu đó.
Tránh O(2^n): Trong các bài toán đệ quy, hãy sử dụng kỹ thuật "Ghi nhớ" (Memoization) để lưu kết quả đã tính, tránh tính lại.