Độ Phức Tạp Thuật Toán (Big O Notation)

Trong Khoa Học Máy Tính, chúng ta không đo tốc độ thuật toán bằng "giây" hay "mili-giây" (vì nó phụ thuộc vào phần cứng). Thay vào đó, chúng ta dùng Big O Notation để đo tốc độ tăng trưởng của thời gian thực thi khi dữ liệu đầu vào ($N$) tăng lên.

Tại sao cần quan tâm?

Code chạy nhanh trên máy tính cá nhân (với N=10) chưa chắc đã chạy ổn trên server production (với N=10 triệu). Big O giúp bạn dự đoán trước thảm họa.

Các Độ Phức Tạp Phổ Biến

Sắp xếp từ "Nhanh nhất" (Tốt nhất) đến "Chậm nhất" (Tệ nhất):

Ký hiệu	Tên gọi	Ví dụ điển hình
$O(1)$	Constant Time	Truy cập phần tử mảng arr[i], tra cứu Hash Map.
$O(\log N)$	Logarithmic Time	Binary Search, tìm kiếm trong cây nhị phân cân bằng.
$O(N)$	Linear Time	Duyệt mảng (Loop), Linear Search.
$O(N\log N)$	Linearithmic Time	Merge Sort, Quick Sort, Heap Sort.
$O(N^2)$	Quadratic Time	Bubble Sort, Selection Sort, vòng lặp lồng nhau.
$O(2^N)$	Exponential Time	Đệ quy Fibonacci (ngây thơ), bài toán tháp Hà Nội.
$O(N!)$	Factorial Time	Liệt kê hoán vị, bài toán người du lịch (TSP).

Biểu Đồ So Sánh

Hãy tưởng tượng $N=100$:

• O(1): 1 bước.
• O(log N): ~7 bước.
• O(N): 100 bước.
• O(N log N): ~700 bước.
• O(N^2): 10,000 bước.
• O(2^N): $1.26\times {10}^{30}$ bước (Máy tính chạy đến tận thế cũng chưa xong).

Space Complexity (Độ Phức Tạp Không Gian)

Ngoài thời gian, chúng ta còn quan tâm đến bộ nhớ (RAM).

• O(1): Chỉ dùng một vài biến phụ (Ví dụ: Bubble Sort).
• O(N): Cần tạo mảng phụ kích thước N (Ví dụ: Merge Sort).

💡 The Trade-off (Sự Đánh Đổi)

Trong kỹ thuật phần mềm, thường có một sự đánh đổi kinh điển: Time vs Space. Bạn có thể làm thuật toán chạy nhanh hơn bằng cách dùng nhiều bộ nhớ hơn (Caching/Memoization), và ngược lại.