Big O Notation là gì? Hiểu độ phức tạp thuật toán từ A đến Z

Khi giải quyết vấn đề bằng code, bạn đã bao giờ tự hỏi "đoạn code này nhanh hay chậm?" chưa? Khi dữ liệu tăng lên 1.000 lần, thời gian xử lý sẽ thay đổi như thế nào?

Big O Notation (ký hiệu Big O) là "ngôn ngữ chung" để so sánh khách quan tốc độ của các thuật toán. Nếu bạn chưa nắm vững nền tảng về thuật toán, hãy đọc Thuật toán là gì trước để hiểu sâu hơn.

Những gì bạn sẽ học được trong bài viết này:

• Ý nghĩa và sự khác biệt của các độ phức tạp chính từ O(1) đến O(2ⁿ)
• 4 ví dụ code Python minh họa thực tế
• Bảng so sánh số phép tính theo kích thước dữ liệu
• Mẹo trả lời phỏng vấn xin việc luôn hữu ích

Big O Notation là gì? Định nghĩa đơn giản

Big O Notation là ký hiệu toán học dùng để biểu diễn độ phức tạp tính toán của một thuật toán. Nó cho thấy số bước xử lý tăng lên như thế nào khi kích thước đầu vào n tăng lên.

Big O Notation biểu thị "giới hạn trên của trường hợp tệ nhất (Worst Case)". Tức là, dù đầu vào là gì đi nữa, nó đảm bảo rằng "tốc độ sẽ không chậm hơn mức này".

Sau khi tính toán độ phức tạp, chỉ giữ lại số hạng bậc cao nhất và bỏ qua các hằng số và số hạng bậc thấp hơn. Ví dụ: 3n² + 2n + 1000 sẽ trở thành O(n²). Hệ số 3, 2n và 1000 đều được bỏ qua.

Tại sao cần đo độ phức tạp tính toán?

Hãy tưởng tượng quầy thu ngân của một cửa hàng tiện lợi. Nếu chỉ có 1 khách, bất kỳ cách xử lý nào cũng nhanh chóng. Nhưng khi số khách tăng lên 1 triệu người, sự khác biệt về thuật toán sẽ tạo ra khoảng cách giữa "vài giây" và "vài ngày".

Ở n=1.000, sự khác biệt có thể chưa rõ ràng, nhưng khi n=1.000.000, sự chênh lệch giữa O(n²) và O(n log n) trở nên rất nghiêm trọng. Các cuộc phỏng vấn tại công ty IT lớn hầu như luôn hỏi về kiến thức này.

Những gì Big O Notation thể hiện

Nó biểu diễn mối quan hệ giữa kích thước đầu vào n và số bước xử lý. n là số lượng dữ liệu cần xử lý.

Có 3 cách nhìn về độ phức tạp:

• Best Case (tốt nhất): Mẫu đầu vào mà thuật toán hoàn thành nhanh nhất
• Average Case (trung bình): Tốc độ với đầu vào điển hình
• Worst Case (tệ nhất): Mẫu đầu vào làm thuật toán chậm nhất

Big O Notation thường lấy Worst Case làm chuẩn. Trong phỏng vấn, hãy tập trung trả lời về "Worst Case là gì".

Các loại Big O Notation chính

Dưới đây là giải thích theo thứ tự từ tốt đến xấu. Hãy kiểm tra định nghĩa, đặc điểm và thuật toán đại diện của mỗi ký hiệu.

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

Định nghĩa: Luôn hoàn thành trong thời gian cố định, bất kể kích thước đầu vào.

Đánh giá: Excellent (Xuất sắc)

Dù dữ liệu tăng bao nhiêu, tốc độ xử lý không thay đổi. Ví dụ điển hình: truy cập mảng bằng chỉ số, tìm kiếm khóa trong từ điển (dict), list.append().

O(log n) — Thời gian logarit (Logarithmic Time)

Định nghĩa: Mỗi lần xử lý, thu hẹp đầu vào xuống một nửa.

Đánh giá: Excellent (Xuất sắc)

Dù n tăng gấp đôi, xử lý chỉ tăng thêm 1 bước. Với 1 triệu bản ghi, tối đa chỉ 20 bước là xong — đây là độ phức tạp rất hiệu quả. Ví dụ điển hình: Tìm kiếm nhị phân (Binary Search).

O(n) — Thời gian tuyến tính (Linear Time)

Định nghĩa: Thời gian xử lý tăng tỷ lệ thuận với kích thước đầu vào.

Đánh giá: Fair (Chấp nhận được)

Nếu dữ liệu tăng 10 lần, xử lý cũng tăng 10 lần. Ví dụ điển hình: Tìm kiếm tuyến tính (Linear Search), duyệt toàn bộ phần tử trong danh sách.

O(n log n) — Thời gian tuyến tính logarit (Linearithmic Time)

Định nghĩa: Độ phức tạp điển hình của các thuật toán sắp xếp hiệu quả sử dụng phương pháp chia để trị (divide and conquer).

Đánh giá: Good (Tốt)

Hầu hết các thuật toán sắp xếp thực tế đều thuộc nhóm này. Ví dụ điển hình: Merge Sort (đảm bảo mọi trường hợp), Quick Sort (trung bình), Heap Sort.

Lưu ý: Quick Sort có thể đạt O(n²) trong trường hợp tệ nhất.

O(n²) — Thời gian bậc hai (Quadratic Time)

Định nghĩa: Vòng lặp lồng nhau hai cấp là mẫu điển hình.

Đánh giá: Bad (Không phù hợp với dữ liệu lớn)

Nếu dữ liệu tăng 10 lần, xử lý tăng 100 lần. Ví dụ điển hình: Bubble Sort, Insertion Sort, Selection Sort.

O(2ⁿ) — Thời gian hàm mũ (Exponential Time)

Định nghĩa: Mỗi lần đệ quy phân nhánh, số lần gọi hàm tăng gấp đôi.

Đánh giá: Horrible (Nên tránh trong thực tế)

Khi chạy fibonacci_naive(30), số lần gọi hàm vượt quá 2.692.537 lần. Chỉ cần n tăng một chút, quá trình xử lý sẽ đạt quy mô không thực tế. Ví dụ điển hình: Cài đặt đệ quy Fibonacci không tối ưu.

Bảng so sánh độ phức tạp

Bảng 1: So sánh tổng quan độ phức tạp

Bảng 2: So sánh số phép tính theo kích thước dữ liệu

Khi n=1.000.000, O(n²) cần tới 1 nghìn tỷ bước. Trong khi đó, O(log n) chỉ cần vỏn vẹn 20 bước. Sự chênh lệch này chính là bản chất của "lựa chọn thuật toán".

Lưu ý: Phép tính O(log n) sử dụng log₂. Trong Big O Notation, sự khác biệt về cơ số chỉ là bội số hằng số nên có thể bỏ qua.

Hiểu độ phức tạp qua code Python

Python là một trong những ngôn ngữ phù hợp nhất để hiểu trực quan về độ phức tạp tính toán. Hãy cùng trải nghiệm từng độ phức tạp qua 4 ví dụ code.

O(1) — Truy cập chỉ số mảng và tra cứu từ điển

Việc truy cập mảng bằng chỉ số và tìm kiếm khóa trong từ điển (dict) đều hoàn thành trong thời gian cố định, bất kể lượng dữ liệu. Đây chính là sức mạnh của O(1).

# O(1): Truy cập mảng bằng chỉ số — thời gian cố định bất kể lượng dữ liệu
arr = [10, 20, 30, 40, 50]
print(arr[2])  # Luôn là O(1) — kết quả: 30

# O(1): Tìm kiếm khóa trong từ điển — xác định ngay lập tức nhờ bảng băm (hash table)
user_scores = {
    "nguyen": 95,
    "tran": 87,
    "le": 92
}
score = user_scores["nguyen"]  # Không phụ thuộc vào kích thước từ điển
print(score)  # 95

# Time Complexity:  O(1)
# Space Complexity: O(1)

O(n) — Tìm kiếm tuyến tính (Linear Search)

Tìm kiếm tuyến tính là kiểm tra từng phần tử từ đầu danh sách theo thứ tự. Nếu giá trị mục tiêu nằm ở cuối, phải duyệt qua toàn bộ phần tử.

# O(n): Kiểm tra lần lượt từng phần tử từ đầu
def linear_search(arr, target):
    n = len(arr)
    for i in range(n):          # Tối đa n vòng lặp → O(n)
        if arr[i] == target:
            return i            # Trả về chỉ số tìm thấy
    return -1                   # Trả về -1 nếu không tìm thấy

arr = [5, 3, 8, 1, 9, 2]
print(linear_search(arr, 8))    # 2

# Best Case:  O(1) — khi giá trị mục tiêu nằm ở đầu danh sách
# Worst Case: O(n) — khi giá trị mục tiêu nằm ở cuối hoặc không tồn tại
# Time Complexity:  O(n)
# Space Complexity: O(1)

O(n²) — Sắp xếp nổi bọt (Bubble Sort)

Vòng lặp lồng nhau hai cấp là ví dụ điển hình tạo ra O(n²). Vòng lặp ngoài lặp n lần, vòng lặp trong cũng lặp n lần, tạo ra tổng cộng n² lần so sánh.

# O(n²): Liên tục so sánh và hoán đổi các phần tử kề nhau để sắp xếp
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):                      # Vòng lặp ngoài: O(n)
        swapped = False
        for j in range(0, n - i - 1):       # Vòng lặp trong: O(n) → tổng O(n²)
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break   # Kết thúc sớm nếu không có hoán đổi (best case là O(n))
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))  # [11, 12, 22, 25, 34, 64, 90]

# Time Complexity:  O(n²) — trường hợp trung bình và tệ nhất
# Space Complexity: O(1)  — hầu như không cần bộ nhớ bổ sung

O(log n) — Tìm kiếm nhị phân (Binary Search)

Mỗi lần xử lý thu hẹp phạm vi tìm kiếm xuống một nửa. Với 1 triệu bản ghi, tối đa chỉ 20 lần so sánh là tìm ra kết quả — hiệu quả đáng kinh ngạc.

# O(log n): Thu hẹp mảng đã sắp xếp xuống một nửa mỗi lần
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = low + (high - low) // 2   # Cách viết tránh tràn số (overflow)
        if arr[mid] == target:
            return mid                  # Tìm thấy
        elif arr[mid] < target:
            low = mid + 1               # Tìm kiếm nửa bên phải
        else:
            high = mid - 1              # Tìm kiếm nửa bên trái
    return -1

arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(arr, 7))    # 3
print(binary_search(arr, 6))    # -1

# Lưu ý: Mảng đầu vào phải được sắp xếp trước
# Best Case:  O(1)     — khi giá trị trung tâm là mục tiêu
# Worst Case: O(log n) — n=1.000.000 tối đa ~20 bước
# Time Complexity:  O(log n)
# Space Complexity: O(1)

Thực hành: Cách dùng List và Dict hiệu quả

Tại sao từ điển (dict) có thể tìm kiếm trong O(1)? Lý do nằm ở cấu trúc nội bộ gọi là "bảng băm (hash table)". Khóa được chuyển đổi bằng hàm băm để tính trực tiếp vị trí lưu trữ trong bộ nhớ, nên có thể truy cập giá trị ngay lập tức mà không phụ thuộc vào lượng dữ liệu.

Trong khi đó, toán tử in của danh sách (list) so sánh từng phần tử từ đầu đến cuối nên có độ phức tạp O(n).

So sánh tốc độ tìm kiếm: List vs Dict

import time

# Chuẩn bị 1 triệu bản ghi
data_list = list(range(1_000_000))
data_dict = {i: True for i in range(1_000_000)}
target = 999_999  # Phần tử cuối — trường hợp tệ nhất cho list

# Tìm kiếm trong list: O(n) — duyệt toàn bộ phần tử đến cuối
start = time.time()
result = target in data_list
print(f"List:  {time.time() - start:.6f} giây")   # ~0.008500 giây

# Tìm kiếm trong dict: O(1) — xác định ngay lập tức bằng hash
start = time.time()
result = target in data_dict
print(f"Dict:  {time.time() - start:.6f} giây")   # ~0.000001 giây

# Time Complexity (List search): O(n)
# Time Complexity (Dict search): O(1) trung bình

Mối quan hệ giữa cấu trúc vòng lặp và độ phức tạp

n = 5

# Vòng lặp 1 cấp → O(n)
for i in range(n):
    print(i)            # Thực thi n lần

# Vòng lặp lồng nhau 2 cấp → O(n²)
for i in range(n):
    for j in range(n):
        print(i, j)     # Thực thi n × n = n² lần

# 2 vòng lặp tuần tự → O(n) + O(n) = O(2n) → O(n)
for i in range(n):
    print(i)
for j in range(n):
    print(j)            # Tổng 2n bước, bỏ qua hệ số nên là O(n)

Chỉ cần có trực giác rằng vòng lặp 1 cấp là O(n), vòng lặp lồng nhau 2 cấp là O(n²), việc review code sẽ trở nên dễ dàng hơn rất nhiều.

Bảng tra cứu nhanh độ phức tạp theo cấu trúc dữ liệu Python

Chuẩn bị Big O Notation cho phỏng vấn kỹ thuật

Trong các buổi phỏng vấn kỹ thuật tại công ty IT lớn, câu hỏi về Big O Notation hầu như luôn xuất hiện. Dù bạn dùng Python, JavaScript hay bất kỳ ngôn ngữ nào, kiến thức về độ phức tạp tính toán đều được yêu cầu chung.

4 dạng câu hỏi thường gặp và cách trả lời

1. "Độ phức tạp thời gian của đoạn code này là gì?"

Quan sát cấu trúc vòng lặp và độ sâu của lồng nhau. Hãy luyện tập trả lời ngay: vòng lặp 1 cấp là O(n), lồng nhau 2 cấp là O(n²), xử lý chia đôi là O(log n).

2. "Làm thế nào để cải thiện code O(n²) thành O(n log n)?"

Với xử lý sắp xếp, sử dụng Merge Sort. Chiến lược cơ bản là thay thế Bubble Sort hoặc Selection Sort bằng thuật toán chia để trị.

3. "Space Complexity của code này là gì?"

Kiểm tra các mảng được cấp phát thêm và call stack của lệnh gọi đệ quy. Lưu ý rằng mỗi lần hàm đệ quy được gọi, một stack frame sẽ được tích lũy.

4. "Tại sao từ điển có thể tìm kiếm trong O(1)?"

Giải thích cơ chế của bảng băm (hash table). Câu trả lời đúng là: "Vì khóa được chuyển đổi bằng hàm băm để tính trực tiếp địa chỉ bộ nhớ, nên không phụ thuộc vào lượng dữ liệu".

Cách trả lời về Best / Average / Worst Case

Trong phỏng vấn, hãy trả lời tập trung vào Worst Case, và nếu có thể đề cập thêm Best và Average Case thì điểm đánh giá sẽ cao hơn.

Worst Case của Quick Sort đạt O(n²) khi việc chọn pivot bị lệch cực đoan (ví dụ: luôn chọn giá trị nhỏ nhất hoặc lớn nhất). Trong khi đó, Merge Sort là thuật toán sắp xếp duy nhất đảm bảo O(n log n) trong mọi trường hợp — đây chính là điểm tạo sự khác biệt trong phỏng vấn.

Kỹ thuật trả lời ngay trong phỏng vấn

• Mỗi cấp độ lồng nhau thêm của vòng lặp, số mũ của n tăng thêm 1
• Bỏ qua tất cả hằng số, hệ số và số hạng bậc thấp (5n² + 3n + 100 → O(n²))
• Nhớ rằng "chỉ Merge Sort mới đảm bảo O(n log n) trong mọi trường hợp"

Nếu bạn muốn học sâu hơn về thuật toán, các khóa học chuyên về cấu trúc dữ liệu và thuật toán trên Udemy rất được khuyến nghị. Với hàng trăm bài tập thực hành và giải thích chi tiết, hiệu quả luyện tập phỏng vấn sẽ tăng đáng kể.

Space Complexity (Độ phức tạp không gian) là gì?

Trong khi Time Complexity biểu thị "tốc độ xử lý (số bước)", thì Space Complexity biểu thị "lượng bộ nhớ sử dụng".

Space Complexity = Không gian bổ sung (Auxiliary Space) + Không gian chiếm bởi dữ liệu đầu vào

Lưu ý rằng call stack của lệnh gọi đệ quy cũng được tính vào Space Complexity. Đệ quy sâu không chỉ tiêu tốn thời gian mà còn tiêu tốn bộ nhớ.

Các loại Space Complexity chính

• O(1) Space: Hầu như không cần bộ nhớ bổ sung (Bubble Sort in-place, Binary Search dạng lặp)
• O(log n) Space: Cần stack bằng độ sâu đệ quy (Binary Search dạng đệ quy)
• O(n) Space: Cần bộ nhớ bằng kích thước đầu vào (mảng phụ của Merge Sort, bảng memoization)
• O(n²) Space: Mảng hai chiều (lưới n×n)

Đánh đổi Time vs Space — Học qua Fibonacci

Dãy Fibonacci là tài liệu học tốt nhất để hiểu cải tiến thuật toán. Hãy so sánh 3 cách tiếp cận để trải nghiệm "sự đánh đổi giữa thời gian và bộ nhớ".

# Cách 1: Đệ quy không tối ưu — Time O(2ⁿ), Space O(n) — Không khuyến nghị
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
# Số lần gọi fib_naive(30) = 2.692.537 lần

# Cách 2: Ghi nhớ (Memoization) — Time O(n), Space O(n) — Thực tế
def fib_memo(n, dp=None):
    if dp is None:
        dp = [-1] * (n + 1)
    if n <= 1:
        return n
    if dp[n] != -1:
        return dp[n]
    dp[n] = fib_memo(n - 1, dp) + fib_memo(n - 2, dp)
    return dp[n]
# Time Complexity:  O(n)  — mỗi giá trị chỉ tính một lần
# Space Complexity: O(n)  — do bảng memoization

# Cách 3: DP từ dưới lên (Bottom-up DP) — Time O(n), Space O(1) — Tối ưu
def fib_optimal(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fib_optimal(10))  # 55
# Time Complexity:  O(n)  — n vòng lặp
# Space Complexity: O(1)  — chỉ dùng 2 biến

Sự chuyển đổi từ Cách 1 sang Cách 3 thể hiện khái niệm "tạm thời dùng bộ nhớ để cải thiện thời gian". Cuối cùng ở Cách 3, cả bộ nhớ lẫn thời gian đều được tối ưu hóa. Nếu bạn có thể giải thích được quá trình tư duy cải tiến như thế này, đánh giá trong phỏng vấn sẽ thay đổi đáng kể.

Các thuật toán liên quan đến Big O Notation

Kiến thức về Big O Notation thực sự phát huy tác dụng khi bạn học các thuật toán cụ thể. Về thuật toán sắp xếp, tìm kiếm, quy hoạch động và độ phức tạp của chúng, hãy xem chi tiết tại Thuật toán là gì.

Bảng tra cứu nhanh độ phức tạp của các thuật toán chính:

Thuật toán sắp xếp

• Bubble Sort: Time O(n²), Space O(1)
• Selection Sort: Time O(n²), Space O(1)
• Merge Sort: Time O(n log n), Space O(n)
• Quick Sort: Time O(n log n) trung bình, Space O(log n)

Thuật toán tìm kiếm

• Linear Search: Time O(n), Space O(1)
• Binary Search: Time O(log n), Space O(1)

Nếu bạn muốn áp dụng kiến thức CS cơ bản vào thiết kế hệ thống, API là gì cũng là tài liệu tham khảo hữu ích.

Câu hỏi thường gặp (FAQ)

Big O Notation có khó không?

Chỉ cần nhớ 6 mẫu cơ bản (O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)) là đủ để xử lý hầu hết các tình huống lập trình hàng ngày. Bằng chứng toán học không cần thiết trong thực tế. Hãy ưu tiên ghi nhớ theo dạng nhận dạng mẫu.

Khi nào thực sự cần dùng Big O Notation?

Khi dữ liệu trở nên lớn (hơn 100.000 bản ghi) hoặc khi bạn được yêu cầu cải thiện hiệu năng hệ thống. Vì hầu như luôn được hỏi trong phỏng vấn, hãy nắm vững trước khi bắt đầu tìm việc.

Thuật toán O(n²) có luôn là xấu không?

Không vấn đề khi n nhỏ (khoảng đến 100 phần tử). Việc cài đặt đơn giản cũng là giá trị quan trọng trong thực tế. Tuy nhiên, nếu n có khả năng tăng lên trong tương lai, hãy sớm cân nhắc cải thiện sang O(n log n).

Sự khác biệt giữa Time Complexity và Space Complexity là gì?

Time Complexity biểu thị tốc độ xử lý (số bước), Space Complexity biểu thị lượng bộ nhớ sử dụng. Hai yếu tố này thường có mối quan hệ đánh đổi — nhiều tình huống dùng bộ nhớ để cải thiện tốc độ (hoặc ngược lại).

Tóm tắt và bước tiếp theo

Hãy ôn lại những điểm quan trọng đã học trong bài viết này:

• Big O Notation là ký hiệu để so sánh khách quan tốc độ thuật toán, biểu thị giới hạn trên của Worst Case
• O(1) và O(log n) là tốt nhất; O(2ⁿ) nên tránh trong thực tế
• Xây dựng trực giác: vòng lặp lồng nhau 2 cấp → O(n²), chia để trị → O(n log n)
• Tìm kiếm trong từ điển (dict) là O(1), trong danh sách (list) là O(n)
• Trong phỏng vấn, tập trung trả lời về Worst Case và đề cập thêm Best / Average để được đánh giá cao
• Time và Space thường có mối quan hệ đánh đổi

Hãy tiến thêm bước tiếp theo với các chủ đề sau:

1. Cấu trúc dữ liệu (Data Structure) (Stack, Queue, HashMap, cây)
2. Cài đặt thuật toán sắp xếp (Merge Sort, Quick Sort)
3. Quy hoạch động (Dynamic Programming) (cách dùng Memoization và Bottom-up DP)

Hãy củng cố nền tảng về sắp xếp và tìm kiếm qua Thuật toán là gì, rồi áp dụng kiến thức CS cơ bản vào thiết kế hệ thống qua API là gì — đây là con đường học tập hiệu quả.

Nếu bạn muốn học thuật toán và cấu trúc dữ liệu một cách có hệ thống, các khóa học chuyên biệt trên Udemy rất được khuyến nghị. Với hàng trăm bài tập thực hành và giải thích chi tiết, bạn sẽ xây dựng được cảm giác về độ phức tạp tính toán cần thiết cho phỏng vấn.