Độ phức tạp thời gian và ký hiệu Big O
Chào các bạn lập trình viên! 🙋🏻♀️
Nếu bạn đang bắt đầu hành trình lập trình của mình, chắc hẳn bạn đã nghe đến khái niệm ký hiệu Big O hoặc độ phức tạp thời gian của một thuật toán. Bạn có thể đã tự hỏi tại sao một giải pháp lại tốt hơn giải pháp khác, mặc dù cả hai đều thực hiện cùng một công việc! Đừng lo lắng nếu bạn cảm thấy đây là một công thức toán học đáng sợ, bài viết này sẽ giúp bạn hiểu rõ về khái niệm này và tầm quan trọng của nó.
Bài viết này là phần một trong hai phần của loạt bài:
- Phần 1 (bài viết này): Độ phức tạp thời gian
- Phần 2 (bài viết tiếp theo): Độ phức tạp không gian
📑 Mục lục
- Ký hiệu Big O là gì?
- Tại sao ký hiệu Big O lại quan trọng?
- Cách tìm ký hiệu Big O
- Các thuộc tính của Big O
- Các độ phức tạp thời gian phổ biến
- Big O, Big Omega và Big Theta
- Bài tập thực hành
- Tài nguyên tham khảo
Ký hiệu Big O là gì?
Thời gian Big O là ngôn ngữ và chỉ số mà chúng ta sử dụng để mô tả hiệu quả của các thuật toán. Nếu không hiểu rõ, bạn không chỉ bị đánh giá thấp mà còn gặp khó khăn trong việc đánh giá các thuật toán và giải pháp cho các bài toán lập trình.
Tại sao ký hiệu Big O lại quan trọng?
Ký hiệu Big O quan trọng vì nhiều lý do:
- So sánh hiệu suất: Nó cung cấp một cách để so sánh hiệu suất của các thuật toán và cấu trúc dữ liệu khác nhau và dự đoán cách chúng sẽ hoạt động khi kích thước đầu vào tăng.
- Phân tích hiệu quả: Giúp phân tích độ hiệu quả của các thuật toán.
- Mô tả yêu cầu: Cung cấp một cách để mô tả cách mà yêu cầu về thời gian chạy hoặc không gian của một thuật toán phát triển khi kích thước đầu vào tăng.
- Lựa chọn thuật toán: Cho phép lập trình viên so sánh các thuật toán khác nhau và chọn thuật toán hiệu quả nhất cho một bài toán cụ thể.
- Tính khả năng mở rộng: Giúp hiểu khả năng mở rộng của các thuật toán và dự đoán cách chúng sẽ hoạt động khi kích thước đầu vào tăng.
- Tối ưu hóa mã: Giúp lập trình viên tối ưu hóa mã và cải thiện hiệu suất tổng thể.
Cách tìm ký hiệu Big O
Để xác định ký hiệu Big O của một thuật toán, bạn có thể làm theo các bước sau:
- Bỏ qua các hạng mục bậc thấp: Chỉ xem xét hạng mục bậc cao nhất.
- Bỏ qua hằng số: Bỏ qua các hằng số liên quan đến hạng mục bậc cao nhất.
Các thuộc tính của Big O
- Tính phản xạ: Đối với bất kỳ hàm f(n), f(n) = O(f(n)).
- Tính truyền: Nếu f(n) = O(g(n)) và g(n) = O(h(n)), thì f(n) = O(h(n)).
- Hằng số: Đối với bất kỳ hằng số c > 0 và các hàm f(n) và g(n), nếu f(n) = O(g(n)), thì cf(n) = O(g(n)).
- Quy tắc tổng: Nếu f(n) = O(g(n)) và h(n) = O(k(n)), thì f(n) + h(n) = O(max(g(n), k(n))). Khi kết hợp các độ phức tạp, chỉ hạng mục lớn nhất chi phối.
- Quy tắc tích: Nếu f(n) = O(g(n)) và h(n) = O(k(n)), thì f(n) * h(n) = O(g(n) * k(n)).
- Quy tắc hợp thành: Nếu f(n) = O(g(n)), thì f(h(n)) = O(g(h(n))).
Các độ phức tạp thời gian phổ biến
| Tên | Ký hiệu | Ý nghĩa | Ví dụ |
|---|---|---|---|
| Hằng số | O(1) | Thời gian chạy là hằng số bất kể kích thước đầu vào | Truy cập phần tử mảng bằng chỉ số, Thêm/xóa vào ngăn xếp, câu lệnh if |
| Logarit | O(log n) | Sau mỗi lần lặp, kích thước đầu vào giảm | Tìm kiếm nhị phân |
| Tuyến tính | O(n) | Thời gian chạy tăng tuyến tính với kích thước đầu vào | Tìm kiếm tuyến tính |
| Siêu tuyến tính | O(n * log n) | Kích thước đầu vào n được xử lý qua log n cấp độ | Quick Sort, Heap Sort, Merge Sort |
| Đa thức | O(n^k) | Ví dụ: O(n^2) Thời gian chạy tỷ lệ thuận với bình phương kích thước đầu vào | Nhân ma trận Strassen, Sắp xếp nổi, Sắp xếp chọn, Sắp xếp chèn, Sắp xếp theo nhóm |
| Hàm mũ | O(k^n) | Ví dụ: O(2^n) Thời gian chạy gấp đôi với mỗi lần thêm vào tập dữ liệu đầu vào | Tháp Hanoi |
| Giai thừa | O(n!) | Thời gian chạy tăng giai thừa với kích thước đầu vào | Mở rộng định thức bằng các phần tử nhỏ, Thuật toán tìm kiếm brute force cho bài toán Nhân viên bán hàng |
Big O, Big Omega và Big Theta
| Ký hiệu | Giải thích |
|---|---|
| Big O (O) | Mô tả giới hạn trên của thời gian chạy của thuật toán. (Mô tả trường hợp tồi tệ nhất của một đầu vào) Thường được sử dụng khi phân tích độ phức tạp thời gian |
| Big Ω (Omega) | Mô tả giới hạn dưới của thời gian chạy của thuật toán. (Mô tả trường hợp tốt nhất của một đầu vào) |
| Big θ (Theta) | Mô tả một giới hạn chặt chẽ, có nghĩa là cả giới hạn trên và dưới đều cùng một bậc. (Khi trường hợp tốt nhất và tồi tệ nhất giống nhau) Nó đại diện cho tỷ lệ tăng trưởng chính xác theo asymptotic. |
Lưu ý: Trường hợp trung bình thường được phân tích riêng và không luôn bằng Θ.
Bài tập thực hành
Hãy xem blog sau để tìm hiểu cách tính toán độ phức tạp thời gian cho hầu hết các tình huống phổ biến một cách chi tiết.
Ngoài ra, tôi rất khuyên bạn nên kiểm tra những bài tập này để kiểm tra kiến thức của mình: Bài tập về ký hiệu Big O - GitHub
Tài nguyên tham khảo
- Sách Cracking the Coding Interview
- Hướng dẫn ký hiệu Big O - GeeksforGeeks
Cảm ơn bạn đã đọc!
Chúc bạn lập trình vui vẻ! 💻😀
