Tra cứu một khoá trong hash table có độ phức tạp trung bình và xấu nhất là bao nhiêu?
- A.Trung bình O(1), xấu nhất O(1)
- B.Trung bình O(1), xấu nhất O(n)
- C.Trung bình O(log n), xấu nhất O(n)
- D.Trung bình O(n), xấu nhất O(n log n)
Đáp án: B
Trung bình O(1), xấu nhất O(n). Hàm băm tốt phân bố khoá đều nên mỗi bucket chỉ giữ vài phần tử. Khi nhiều khoá va chạm về cùng bucket, thao tác suy biến thành duyệt tuyến tính danh sách trong bucket đó.
Nguồn tham khảo