[DSA] Big O Notation
Vấn đề
Nếu có nhiều function thực hiện cùng 1 chức năng thì dựa vào đâu mà ta xác định được function nào là tốt nhất?
Cơ sở nào để đánh giá code performance, trade-offs khi lựa chọn các cách tiếp cận?
Làm thế nào để đánh giá được đoạn code nào là tốt hơn?
- Tốc độ thực thi?
- Cùng 1 đoạn code nhưng với thiết bị khác nhau thì thời gian thực thi cũng khác nhau. Thậm chí cùng 1 thiết bị, thời gian thực thi cũng có sự sai khác dù đoạn code là không đổi.
- Thậm chí ngôn ngữ lập trình cũng ảnh hưởng đến tốc độ thực thi.
- Ít tốn memory?
- Dễ đọc?
Nếu không phải dựa vào thời gian thực thi thì ta dựa vào đâu để đánh giá chất lượng code? Đó là đếm số lần mà máy tính cần thực hiện một phép toán.
Các phép toán mà máy tính cần thực thi:
- Cộng, trừ, nhân, chia
- Gán giá trị
- So sánh
Giới thiệu về Big O
Big O dùng để biểu diễn độ phức tạp của thuật toán, giúp đánh giá thời gian chạy (runtime) của thuật toán tăng như thế nào khi đầu vào tăng, và bộ nhớ cần sử dụng
Có 2 loại độ phức tạp của thuật toán:
- Độ phức tạp thời gian (Time complexity)
- Độ phức tạp không gian (Space complexity)
Độ phức tạp thời gian (Time complexity)
Thời gian chạy (runtime) của thuật toán tăng như thế nào khi đầu vào tăng.
Các loại độ phức tạp phổ biến
| Ký hiệu | Tên | Mô tả |
|---|---|---|
| O(1) | Hằng số | Thuật toán chạy với số lần không thay đổi |
| O(log n) | Logarithmic | Giảm nhanh số lần chạy khi dữ liệu tăng |
| O(n) | Tuyến tính | Tăng trực tiếp với dữ liệu |
| O(n log n) | Tuyến tính nhân logarithmic | Thường gặp trong sắp xếp |
| O(n^2) | Bậc hai | Tăng rất nhanh khi dữ liệu lớn |
| O(2^n) | Exponential | Rất chậm, thường gặp trong bài toán quy hoạch |
| O(n!) | Giai thừa | Cực kỳ chậm |
Rút gọn Big O
- Bỏ qua hằng số:
O(2n) ~ O(n)O(n + 10) ~ O(n)
- Giữ lại thuật ngữ có tốc độ tăng trưởng nhanh nhất, bỏ bớt các thuật ngữ nhỏ hơn:
O(n + log n) → O(n),O(n^2 + n) → O(n^2)
Độ phức tạp không gian (Space complexity)
Đo lường bộ nhớ mà thuật toán sử dụng.
Độ phức tạp của không gian trong Javascript:
- Hầu hết primitives types (
boolean,number,undefined,null) là hằng số: O(1) - Kiểu
string: O(n) (n là độ dài chuỗi) - Kiểu dữ liệu tham chiếu (reference types) như object, array: O(n)
Kết luận
Để đo lường được tính hiệu quả của giải thuật ta dựa vào Big O
Có 2 thông số cần quan tâm khi xây dựng giải thuật là số lần mà máy tính thực hiện các phép toán (độ phức tạp thời gian) và bộ nhớ sử dụng (độ phức tạp không gian)
All rights reserved
