Big O
date
Mar 31, 2026
slug
big-o-thuat-toan
status
Published
tags
NodeJs
Backend
summary
Độ phức tạp của thuật toán
type
Post
- Big O không đo thời gian thực tế mà đo tốc độ tăng trưởng của thuật toán khi input lớn hơn. Khi nói một thuật toán có time complexity là O(n), nó chỉ quan tâm đến tốc độ tăng trưởng, không phải thời gian chạy cụ thể.
Vậy với mình, Big O có nghĩa là: với input đầu vào có kích thước N, số phép toán cần thực hiện sẽ tăng theo O(n), O(n²), ..., tùy thuộc vào thuật toán. Khi N càng lớn, số phép toán tăng theo độ phức tạp của thuật toán.
=> Big O không quan tâm đến thời gian chạy chính xác, nhưng giúp đánh giá xu hướng tốc độ tăng trưởng khi N lớn.
- Bỏ Qua Hệ Số Và Các Thành Phần Nhỏ Ví dụ: 5N + 100 -> O(N) (bỏ qua hệ số 5 và số hằng 100). N² + 3N + 7 -> O(N²) (chỉ giữ bậc lớn nhất N²).
Lý do: Khi N đủ lớn, bậc lớn nhất quyết định toàn bộ độ phức tạp.
- Space Complexity Hoạt Động Tương Tự
Nếu thuật toán sử dụng mảng hoặc danh sách có kích thước phụ thuộc vào N, nó sẽ có O(N) space complexity.
Nếu chỉ sử dụng một số biến cố định không tăng theo N, thì Space Complexity là O(1).
Đệ quy cũng ảnh hưởng đến Space Complexity, vì mỗi lời gọi hàm lưu trạng thái trên stack.
Ví dụ, đệ quy có độ sâu N sẽ có Space Complexity O(N), ngay cả khi không dùng mảng phụ.