Big O Notation

Big O là gì?

Big O là ngôn ngữ chung để lập trình viên mô tả hiệu năng của một thuật toán khi dữ liệu đầu vào (Input) tăng lên. Chúng ta quan tâm đến:

1. Time Complexity: Thời gian chạy tăng nhanh thế nào?
2. Space Complexity: Bộ nhớ sử dụng tăng nhanh thế nào?

Các cấp độ phổ biến (Từ Nhanh -> Chậm)

1. $O(1)$ - Constant Time (Hằng số)

Tốc độ không đổi, bất kể input lớn cỡ nào. Ví dụ: Truy cập phần tử mảng theo index, Hash Map lookup.

const arr = [10, 20, 30];
console.log(arr[0]); // O(1)

2. $O(\log n)$ - Logarithmic Time

Thường gặp trong các thuật toán chia để trị (Divide and Conquer). Mỗi bước loại bỏ một nửa dữ liệu. Ví dụ: Binary Search. Tìm kiếm trong danh bạ điện thoại 1 triệu số chỉ mất khoảng 20 bước ($2^{20} \approx 10^6$).

// Tìm kiếm nhị phân
while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    // ...
}

3. $O(n)$ - Linear Time (Tuyến tính)

Duyệt qua từng phần tử của input một lần. Ví dụ: Vòng lặp for, tìm max/min, map, filter.

for (let i = 0; i < n; i++) {
    console.log(i);
}

4. $O(n \log n)$ - Log Linear

Thường là hiệu năng tốt nhất của các thuật toán Sắp xếp (Sorting) trên tập dữ liệu tổng quát. Ví dụ: Quick Sort, Merge Sort, phương thức Array.prototype.sort() của JS/V8.

nums.sort((a, b) => a - b); // O(n log n)

5. $O(n^2)$ - Quadratic Time (Bình phương)

Hai vòng lặp lồng nhau. Hiệu năng rất tệ khi $n$ lớn. Ví dụ: Bubble Sort, kiểm tra chuỗi trùng lặp brute-force.

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        // ...
    }
}

6. $O(2^n)$ - Exponential (Số mũ)

Mỗi phần tử thêm vào làm số lượng tính toán tăng gấp đôi. Thường gặp trong đệ quy không tối ưu. Ví dụ: Fibonacci đệ quy.

function fib(n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

Space Complexity (Độ phức tạp không gian)

Không chỉ thời gian, bộ nhớ cũng quan trọng.

• $O(1)$: Chỉ dùng một vài biến đơn lẻ (let i = 0, let sum = 0).
• $O(n)$: Tạo ra mảng mới, Set mới chứa $n$ phần tử. Hoặc đệ quy chiều sâu $n$ (Call Stack).

Tại sao Frontend cần quan tâm?

1. Render Blocking: Một hàm $O(n^2)$ chạy trong quá trình render có thể làm đơ UI nếu list item lớn.
2. Memory Leaks: Sử dụng cấu trúc dữ liệu sai (ví dụ lưu trữ vô hạn vào mảng $O(n)$ mà không clear) sẽ làm crash tab trình duyệt.