Độ phức tạp

Độ phức tạp mô tả thời gian hoặc bộ nhớ tăng thế nào theo kích thước đầu vào n. O(f(n)) là chặn trên tiệm cận và bỏ qua hệ số hằng cùng các hạng nhỏ hơn khi n đủ lớn. Cần nêu rõ đang xét trường hợp tốt, trung bình hay xấu nhất vì ký hiệu O tự nó không cho biết điều đó.

Lĩnh vực: Giải thuật & cấu trúc dữ liệu

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Bài giảng dùng khái niệm này

• Tìm kiếm mù: BFS, DFS, UCS & IDSTri thức & Tìm kiếm
• Tìm kiếm kinh nghiệm: Greedy & A*Tri thức & Tìm kiếm
• Tìm kiếm đối kháng: Minimax & Alpha–BetaTri thức & Tìm kiếm
• Phụ lục A: NumPy nâng caoXử lý dữ liệu
• Dữ liệu lớn & mô hình thuật toánGiải thuật dữ liệu
• Phân tích độ phức tạpCTDL & Giải thuật
• Thuật toán sắp xếpCTDL & Giải thuật
• Thuật toán tìm kiếmCTDL & Giải thuật

Giải thích kỹ thuật

Big-O, Θ và Ω. O là chặn trên tiệm cận. Ω là chặn dưới. Θ là chặn trên và dưới cùng bậc. Một thuật toán Θ(n) cũng thuộc $O(n^2)$, nhưng $O(n^2)$ là mô tả kém chặt hơn.

Phải phân biệt thời gian, bộ nhớ và mô hình tính toán. O(n) không tự nghĩa là “trường hợp xấu nhất”: Trường hợp đang xét cần được nêu riêng.

Ví dụ

Duyệt n phần tử tốn O(n). Hai lồng nhau đều chạy n lần thường tốn $O(n^2)$.

Khi nào cần dùng?

So sánh giải thuật và tác động khi dữ liệu tăng.

Câu hỏi ôn lại

Tăng n gấp đôi, số bước tỷ lệ $n^2$ tăng khoảng bao nhiêu lần?

Xem đáp án

4 lần.

Thuật ngữ liên quan

• Heuristic
• Hàng đợi ưu tiên
• Đồ thị