Big O Complexity Cheat Sheet for Coding Interviews

Tài liệu này là một bảng tổng hợp (cheat sheet) về độ phức tạp thuật toán (Big O Notation) nhằm giúp các lập trình viên chuẩn bị cho phỏng vấn kỹ thuật, đặc biệt trong lĩnh vực khoa học dữ liệu và lập trình phần mềm.

1. Tổng Quan về Big O Notation

Big O Notation là một cách biểu diễn độ phức tạp thời gian (time complexity) và độ phức tạp không gian (space complexity) của thuật toán. Nó mô tả mức độ tăng trưởng của tài nguyên sử dụng khi kích thước đầu vào tăng lên.

Big O giúp trả lời câu hỏi: “Điều gì sẽ xảy ra với hiệu suất của thuật toán khi kích thước đầu vào tăng?”
Chỉ tập trung vào trường hợp xấu nhất (worst-case scenario).
Bỏ qua hằng số và các hệ số nhỏ, chỉ quan tâm đến xu hướng tăng trưởng của thuật toán.

Ví dụ:

Một thuật toán chạy 2n bước hoặc 5n bước vẫn được biểu diễn là O(n) vì chúng có cùng xu hướng tăng trưởng.

2. Các Loại Độ Phức Tạp Thuật Toán Chính

Dưới đây là các loại Big O phổ biến được đề cập trong tài liệu:

O(1) – Constant Time (Thời Gian Hằng Số)

Thời gian thực thi không thay đổi, bất kể kích thước đầu vào.

Ví dụ: Truy xuất phần tử từ một mảng (arr[i]).
Ứng dụng thực tế:
- Truy vấn giá trị trong hash table.
- Thêm/xóa phần tử trong stack hoặc queue.

✔ Hiệu suất: Tốt nhất (không phụ thuộc vào kích thước đầu vào).

O(log n) – Logarithmic Time (Thời Gian Logarit)

Thời gian thực thi tăng theo logarit của kích thước đầu vào. Khi dữ liệu tăng gấp đôi, thuật toán chỉ thêm một vài bước.

Ví dụ:
- Tìm kiếm nhị phân (Binary Search)
- Cây nhị phân cân bằng (Balanced Binary Tree – AVL, Red-Black Tree)
Ứng dụng thực tế:
- Tìm kiếm trong danh sách được sắp xếp.
- Các thuật toán phân chia để trị (Divide and Conquer).

✔ Hiệu suất: Rất tốt (hiệu quả cho các tập dữ liệu lớn).

O(n) – Linear Time (Thời Gian Tuyến Tính)

Thời gian thực thi tăng tuyến tính với kích thước đầu vào.

Ví dụ:
- Duyệt mảng (Array Traversal)
- Tìm kiếm tuyến tính (Linear Search)
Ứng dụng thực tế:
- Duyệt qua danh sách hoặc chuỗi ký tự.
- Tìm phần tử nhỏ nhất/lớn nhất trong một danh sách chưa sắp xếp.

✔ Hiệu suất: Tốt, nhưng có thể được cải thiện bằng cách tối ưu thuật toán.

O(n log n) – Linearithmic Time (Thời Gian Tuyến Tính Nhân Logarit)

Mỗi lần duyệt danh sách cần thực hiện một phép toán logarit.

Ví dụ:
- Thuật toán sắp xếp Merge Sort, QuickSort (trường hợp trung bình).
- Một số thuật toán chia để trị (Divide and Conquer).
Ứng dụng thực tế:
- Hầu hết các thuật toán sắp xếp hiệu quả.
- Tìm cặp điểm gần nhất trong mặt phẳng (Closest Pair of Points).

✔ Hiệu suất: Khá tốt, phổ biến trong các thuật toán sắp xếp.

O(n²) – Quadratic Time (Thời Gian Bình Phương)

Thời gian thực thi tăng theo bình phương kích thước đầu vào.

Ví dụ:
- Thuật toán sắp xếp đơn giản (Bubble Sort, Selection Sort).
- Duyệt qua tất cả cặp phần tử trong danh sách (Nested Loops).
Ứng dụng thực tế:
- So sánh tất cả cặp phần tử trong một danh sách.
- Các thuật toán tìm đường trong đồ thị đơn giản.

❌ Hiệu suất: Kém, không phù hợp với dữ liệu lớn.

O(2ⁿ) – Exponential Time (Thời Gian Hàm Mũ)

Thời gian thực thi tăng gấp đôi với mỗi phần tử đầu vào thêm vào.

Ví dụ:
- Tính dãy Fibonacci bằng đệ quy không tối ưu (fib(n) = fib(n-1) + fib(n-2)).
- Tạo tập con (Power Set).
Ứng dụng thực tế:
- Các bài toán đồ thị yêu cầu kiểm tra tất cả khả năng (Brute Force).
- Một số bài toán tối ưu hóa.

❌ Hiệu suất: Rất kém, cần tránh nếu có thể.

O(n!) – Factorial Time (Thời Gian Giai Thừa)

Thời gian thực thi tăng cực nhanh, không thể áp dụng với dữ liệu lớn.

Ví dụ:
- Tìm tất cả hoán vị của một tập hợp (n! hoán vị).
- Giải bài toán người du lịch (Travelling Salesman Problem – TSP) bằng Brute Force.
Ứng dụng thực tế:
- Các thuật toán thử tất cả cách sắp xếp có thể.
- Một số bài toán đồ thị phức tạp.

❌ Hiệu suất: Cực kỳ kém, chỉ dùng cho bài toán nhỏ.

3. Bảng Tổng Hợp Độ Phức Tạp Thuật Toán

Tên	Mô tả	Ứng dụng thực tế	Hiệu suất
O(1)	Thời gian hằng số	Truy xuất mảng, hash table	Xuất sắc
O(log n)	Thời gian logarit	Binary Search, AVL Tree	Rất tốt
O(n)	Thời gian tuyến tính	Duyệt mảng, tìm kiếm tuyến tính	Tốt
O(n log n)	Giữa tuyến tính và bình phương	Merge Sort, Quicksort	Khá tốt
O(n²)	Thời gian bình phương	Bubble Sort, Nested Loops	Kém
O(2ⁿ)	Thời gian hàm mũ	Đệ quy Fibonacci, Power Set	Rất kém
O(n!)	Thời gian giai thừa	TSP, hoán vị	Cực kỳ kém

4. Kết Luận và Ứng Dụng

Big O giúp đánh giá hiệu suất thuật toán và tránh chọn thuật toán kém tối ưu.
Trong phỏng vấn lập trình, bạn cần nêu rõ độ phức tạp của thuật toán và cách tối ưu hóa.
Luôn cân nhắc trade-off giữa tốc độ (time complexity) và bộ nhớ (space complexity).

📌 Mẹo quan trọng:

Luôn phân tích thời gian và không gian của thuật toán.
Biết cách tối ưu thuật toán từ O(n²) xuống O(n log n) hoặc O(n) nếu có thể.
Áp dụng các cấu trúc dữ liệu phù hợp (Hash Table, Binary Search, Trees) để tối ưu Big O.

🚀 Thực hành giải bài toán thực tế để nắm vững Big O!