📝 Ví dụ phân tích Big O

Hiểu lý thuyết Big O là một chuyện, nhìn vào một đoạn code lạ và suy ra ngay độ phức tạp của nó lại là một kỹ năng khác - cần luyện qua ví dụ. Trang này đi qua vài bài toán quen thuộc, so sánh cách giải chậm và cách giải nhanh hơn, để thấy rõ độ phức tạp thay đổi thế nào khi đổi thuật toán.

Ví dụ 1: Tổng các số từ 1 đến n

Cách 1 - vòng lặp: cộng dồn từng số một, n bước.

def sum_loop(n):
    res = 0
    for i in range(1, n + 1):
        res += i
    return res  # O(n)

Cách 2 - công thức Gauss: 1 + 2 + ... + n = n(n+1)/2, tính trực tiếp bằng một phép nhân và một phép chia, không cần lặp.

def sum_formula(n):
    return n * (n + 1) // 2  # O(1)

Đây là minh họa rõ nhất cho việc thuật toán quyết định độ phức tạp, không phải ngôn ngữ hay cách viết code: cùng một bài toán, đổi cách tiếp cận đưa độ phức tạp từ tuyến tính xuống hằng số.

Ví dụ 2: Tìm phần tử trùng lặp

Cho một mảng, kiểm tra có phần tử nào xuất hiện từ 2 lần trở lên không.

Cách 1 - so sánh từng cặp: với mỗi phần tử, so sánh với tất cả phần tử còn lại.

def has_duplicate_brute(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):   # so mọi cặp (i, j)
            if arr[i] == arr[j]:
                return True
    return False  # O(n²)

Cách 2 - dùng hash set: đánh đổi bộ nhớ lấy tốc độ - lưu lại những gì đã thấy, tra cứu tức thời thay vì so sánh tuần tự.

def has_duplicate_fast(arr):
    seen = set()
    for x in arr:
        if x in seen:      # tra cứu O(1) trung bình
            return True
        seen.add(x)
    return False  # O(n) thời gian, O(n) bộ nhớ phụ trội

Đây là một khuôn mẫu (pattern) cực kỳ phổ biến: bất cứ khi nào thấy vòng lặp lồng nhau chỉ để “tra cứu xem đã gặp chưa”, hãy nghĩ ngay đến hash table - đánh đổi O(n) bộ nhớ để giảm độ phức tạp thời gian từ O(n²) xuống O(n).

Ví dụ 3: Binary Search

Tìm một giá trị trong mảng đã sắp xếp, bằng cách liên tục thu hẹp một nửa khoảng tìm kiếm.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # O(log n)

Cách suy ra O(log n) mà không cần đếm từng bước: mỗi vòng lặp loại bỏ đúng một nửa dữ liệu còn lại, nên số vòng lặp cần thiết chính là số lần bạn có thể chia đôi n cho tới khi còn 1 phần tử - đó là định nghĩa của log₂n.

Ví dụ 4: Đọc vòng lặp lồng nhau

Không phải mọi vòng lặp lồng nhau đều là O(n²). Ba dạng dưới đây trông giống nhau nhưng có độ phức tạp khác hẳn:

# Dạng A: hai vòng lặp độc lập, chạy tuần tự -> CỘNG
for i in range(n):
    ...
for j in range(m):
    ...
# O(n + m)

# Dạng B: vòng trong phụ thuộc vào n, lồng trong vòng ngoài -> NHÂN
for i in range(n):
    for j in range(n):
        ...
# O(n²)

# Dạng C: vòng trong co lại dần theo vòng ngoài
for i in range(n):
    for j in range(i):     # chạy i lần, không phải n lần
        ...
# Tổng số bước: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 -> vẫn O(n²)

Dạng C dễ gây nhầm lẫn nhất: nhìn thoáng qua tưởng “ít việc hơn” vì vòng trong ngắn dần, nhưng tổng số bước vẫn là một cấp số cộng có tổng tỷ lệ với n² - bậc độ phức tạp không đổi, chỉ hằng số nhân giảm đi (khoảng một nửa).

Bảng tổng hợp

Bài toán	Cách chậm	Cách nhanh	Đánh đổi
Tổng 1..n	O(n) vòng lặp	O(1) công thức	Không có - công thức luôn thắng
Tìm trùng lặp	O(n²) so cặp	O(n) hash set	Tốn thêm O(n) bộ nhớ
Tìm kiếm	O(n) linear search	O(log n) binary search	Yêu cầu dữ liệu đã sắp xếp