Big-O notation là gì?

Question

Accepted Answer

**Big-O** mô tả cách thời gian chạy hoặc bộ nhớ của một thuật toán tăng lên khi kích thước đầu vào **n** tăng. Nó nắm bắt hành vi tiệm cận trong *trường hợp xấu nhất*, bỏ qua các hằng số và các số hạng bậc thấp.

## Ý tưởng

Chúng ta quan tâm đến tốc độ tăng trưởng, không phải số bước chính xác. O(2n + 5) đơn giản là **O(n)** vì khi n lớn dần, các hằng số và số hạng nhỏ hơn không còn quan trọng.

## Các lớp phổ biến

| Big-O | Tên | Ví dụ |
|-------|------|---------|
| O(1) | hằng số | truy cập mảng theo chỉ số |
| O(log n) | logarit | binary search |
| O(n) | tuyến tính | quét một danh sách |
| O(n log n) | tuyến tính-logarit | merge sort |
| O(n²) | bậc hai | vòng lặp lồng nhau |
| O(2ⁿ) | hàm mũ | sinh tập con thô sơ |

## Ví dụ

```python
def has_duplicate(nums):
    for i in range(len(nums)):        # vòng lặp ngoài: n
        for j in range(i + 1, len(nums)):  # vòng lặp trong: n
            if nums[i] == nums[j]:
                return True
    return False
# vòng lặp lồng nhau -> O(n^2) thời gian, O(1) bộ nhớ
```

## Những cạm bẫy

Big-O che giấu các hằng số: một thuật toán O(n) với hằng số khổng lồ có thể thua O(n log n) trên đầu vào nhỏ. Cũng cần theo dõi độ phức tạp **bộ nhớ**, không chỉ thời gian.

## Tại sao điều này quan trọng

Big-O cho phép bạn so sánh các thuật toán mà không cần chạy chúng hay lo lắng về phần cứng.

Nó dự đoán giải pháp nào sẽ trụ vững khi đầu vào tăng từ hàng trăm lên hàng triệu — sự khác biệt giữa một tính năng có khả năng mở rộng và một tính năng bị timeout.

Đây là vốn từ vựng mà mọi kỹ sư đều dùng để lập luận về hiệu năng.

O(1)	hằng số	truy cập mảng theo chỉ số
O(log n)	logarit	binary search
O(n)	tuyến tính	quét một danh sách
O(n log n)	tuyến tính-logarit	merge sort
O(n²)	bậc hai	vòng lặp lồng nhau
O(2ⁿ)	hàm mũ	sinh tập con thô sơ