Để đánh giá một thuật toán "tốt" hay "xấu", người ta không dựa vào thời gian chạy tính bằng giây (vì thời gian này phụ thuộc vào cấu hình phần cứng của từng máy tính). Thay vào đó, người ta đo đếm số lượng phép tính cơ bản mà thuật toán thực hiện theo kích thước dữ liệu đầu vào $N$.
Độ phức tạp thời gian (Time Complexity): Hàm số $T(N)$ biểu diễn số lượng phép tính máy tính phải thực hiện khi kích thước đầu vào là $N$.
Độ phức tạp bộ nhớ (Space Complexity): Hàm số $S(N)$ biểu diễn lượng bộ nhớ bổ sung mà thuật toán cần cấp phát thêm trong quá trình vận hành.
Trong thực tế kỹ thuật, người ta quan tâm nhất đến giới hạn trên (Upper Bound) của khối lượng tính toán – tức là thuật toán sẽ tệ đến mức nào trong kịch bản xấu nhất. Ký hiệu Big-O biểu diễn tốc độ tăng trưởng của hàm số khi $N$ tiến đến vô cùng ($N \to \infty$).
Ta nói $T(N) = O(f(N))$ nếu tồn tại các hằng số dương $c$ và $N_0$ sao cho:
| Ký hiệu Big-O | Tên gọi | Ví dụ thuật toán / Thao tác |
| $O(1)$ | Hằng số (Constant) | Truy cập phần tử mảng qua chỉ số arr[i], phép cộng/trừ cơ bản |
| $O(\log N)$ | Lôgarit (Logarithmic) | Tìm kiếm nhị phân (Binary Search) |
| $O(N)$ | Tuyến tính (Linear) | Duyệt mảng 1 vòng lặp để tìm Max/Min |
| $O(N \log N)$ | Tuyến tính - Lôgarit | Merge Sort, Quick Sort (trung bình) |
| $O(N^2)$ | Bậc hai (Quadratic) | 2 vòng lặp lồng nhau (Bubble Sort, Selection Sort) |
| $O(2^N)$ | Mũ (Exponential) | Đệ quy Fibonacci thuần túy, duyệt tất cả tập con |
| $O(N!)$ | Giai thừa (Factorial) | Duyệt tất cả hoán vị (Bài toán người giao hàng - TSP) |
Khi phân tích một hàm số $T(N)$ phức tạp, ta áp dụng 2 quy tắc toán học:
Bỏ qua hằng số nhân: $O(c \cdot f(N)) = O(f(N))$.
Ví dụ: Nếu thuật toán thực hiện $T(N) = 3N + 5$ phép tính, độ phức tạp vẫn là $O(N)$.
Chỉ giữ lại cấp tăng trưởng cao nhất: Nếu $T(N) = f(N) + g(N)$ và $g(N)$ tăng trưởng chậm hơn $f(N)$, thì $O(T(N)) = O(f(N))$.
Ví dụ: $T(N) = N^2 + 100N + 5000 \Rightarrow O(N^2)$.
# 1. Độ phức tạp O(1) - Thời gian không đổi bất kể size của arr
def get_first_element(arr):
return arr[0] # Đúng 1 phép tính
# 2. Độ phức tạp O(N) - 1 vòng lặp chạy N lần
def print_all_elements(arr):
for item in arr: # Chạy N lần
print(item)
# 3. Độ phức tạp O(N^2) - 2 vòng lặp lồng nhau
def print_all_pairs(arr):
n = len(arr)
for i in range(n): # Vòng lặp ngoài: N lần
for j in range(n): # Vòng lặp trong: N lần
print(arr[i], arr[j]) # Tổng số lần thực hiện: N * N = N^2
Cho đoạn mã giả sau, hãy xác định độ phức tạp thời gian $O(f(N))$ trong kịch bản xấu nhất:
def complex_algorithm(arr):
n = len(arr)
# Đoạn 1
for i in range(n):
print(arr[i])
# Đoạn 2
for i in range(n):
for j in range(n):
if arr[i] == arr[j]:
print("Match")Viết một hàm Python has_duplicate(arr) kiểm tra xem trong mảng arr có tồn tại ít nhất hai phần tử trùng nhau hay không.
Yêu cầu 1: Viết hàm theo cách đơn giản nhất (dùng 2 vòng lặp lồng nhau). Xác định độ phức tạp thời gian $O(?)$ và bộ nhớ $O(?)$.
Yêu cầu 2: Tìm cách tối ưu hàm trên để độ phức tạp thời gian đạt $O(N)$ bằng cách sử dụng cấu trúc dữ liệu set (Bảng băm).