Độ phức tạp thuật toán (Big-O)
Độ phức tạp thời gian và không gian của thuật toán và cấu trúc dữ liệu thông dụng. Gợi ý: với mỗi thẻ, tự giải thích vì sao ra kết quả đó.
Tạo bởi Thư viện Flashcard
Xem trước thẻ
Mặt trước
Big-O dùng để làm gì?
Mặt sau
Mô tả cận trên tốc độ tăng của thời gian (hoặc bộ nhớ) theo kích thước đầu vào n khi n lớn.
Mặt trước
O(1) nghĩa là gì?
Mặt sau
Thời gian hằng số, không phụ thuộc n.
Mặt trước
O(log n) nghĩa là gì?
Mặt sau
Tăng rất chậm; mỗi bước giảm bài toán đi một phần (thường một nửa).
Mặt trước
O(n) nghĩa là gì?
Mặt sau
Thời gian tăng tuyến tính theo n.
Mặt trước
O(n log n) thường gặp ở đâu?
Mặt sau
Các thuật toán sắp xếp so sánh hiệu quả như merge sort, heap sort, quick sort (trung bình).
Mặt trước
O(n²) thường gặp ở đâu?
Mặt sau
Hai vòng lặp lồng nhau cùng chạy theo n, ví dụ bubble sort, insertion sort xấu nhất.
Mặt trước
O(2^n) thường gặp ở đâu?
Mặt sau
Đệ quy phân nhánh kép không nhớ, ví dụ Fibonacci đệ quy ngây thơ, liệt kê mọi tập con.
Mặt trước
O(n!) thường gặp ở đâu?
Mặt sau
Liệt kê mọi hoán vị, ví dụ giải Người bán hàng bằng vét cạn.
Mặt trước
Sắp xếp các độ phức tạp từ nhanh đến chậm khi n lớn?
Mặt sau
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!).
Mặt trước
Vì sao bỏ hằng số và số hạng bậc thấp trong Big-O?
Mặt sau
Khi n rất lớn, số hạng bậc cao nhất quyết định tốc độ tăng. O(3n + 10) viết là O(n).
và 37 thẻ khác