O (1) tìm kiếm băm?

Question

Tôi chạy qua một xác nhận rằng HashSet <T> .Contains() là một hoạt động O (1). Điều này làm tôi ngạc nhiên vì mọi cuộc thảo luận về băm tôi gặp phải đều đề cập đến khả năng va chạm, có khả năng dẫn đến thời gian chạy O (n).

Tò mò, tôi đã xem tài liệu cho HashSet <T> .Có và cũng có HashTable.Contains. Tài liệu cho cả hai phương pháp đều đưa ra tuyên bố đó.

Khi tôi nhìn vào phản xạ, HashSet <T> .Contains() được thực hiện với vòng lặp for, trải qua danh sách các vị trí chứa các giá trị có cùng giá trị băm.

Bây giờ phải thừa nhận rằng, những thảo luận tương tự về băm cũng đã đề cập rằng một thuật toán băm tốt tránh va chạm và trong những trường hợp đó tra cứu thực sự sẽ là O (1). Nhưng sự hiểu biết của tôi về ký hiệu Big O là nó là thời gian chạy trường hợp xấu nhất, không tốt nhất.

Vì vậy, yêu cầu O (1) không chính xác? Hay tôi đang thiếu một cái gì đó?

Answer 1

Nhưng sự hiểu biết của tôi về ký hiệu Big O là thời gian chạy trường hợp xấu nhất, không tốt nhất.

Thật không may, không có "chuẩn" cho Big-O khi mô tả thuật toán. Thông thường, nó được sử dụng để mô tả trường hợp chung hoặc trung bình - không phải trường hợp xấu nhất.

Từ Wikipedia:

... ký hiệu này hiện nay thường xuyên cũng được sử dụng trong việc phân tích các thuật toán để mô tả việc sử dụng một thuật toán của các nguồn tài nguyên tính toán: trường hợp xấu nhất hoặc trường hợp trung bình ...

Trong trường hợp này, nó mô tả trường hợp tiêu chuẩn, được cho phép băm thích hợp. Nếu bạn có băm thích hợp tại chỗ, hành vi giới hạn sẽ không đổi đối với kích thước N, do đó O (1).

Answer 2

Nói chung, đó là O (1).

Answer 3

Không, Big O không xác định "trường hợp xấu nhất", nó xác định giới hạn. Các tra cứu dựa trên Hash (với các thuật toán băm tốt cung cấp phân phối giá trị hiệu quả và tốc độ va chạm thấp) tiến tới một giá trị không đổi khi số lượng các mục tăng lên (chúng sẽ không bao giờ đạt được hoặc giá trị không đổi đó, nhưng đó là điểm của nó là giới hạn).

Answer 4

Tôi tin rằng nó có nghĩa là O (1) trung bình.

Answer 5

Sự hiểu biết của tôi về Big Oh là "trường hợp xấu nhất" thường là tham chiếu đến số lượng yếu tố có liên quan. Vì vậy, nếu một hàm được thực hiện O (n) với 10 phần tử, nhưng O (n bình phương) với 100 hoặc nhiều hơn (không chắc chắn thuật toán thực sự tồn tại), thì thuật toán được coi là O (n bình phương).

Answer 6

O (1) không nhất thiết có nghĩa là "trường hợp xấu nhất". Đối với băm, người ta thường nói rằng thời gian tra cứu "dự kiến" là O (1), vì xác suất của các va chạm băm nhỏ.

Answer 7

Để có bảng băm được triển khai đúng, tra cứu có độ phức tạp thời gian không đổi amortized.

Trong thực tế, một lần tra cứu duy nhất có thể là O (n) trong trường hợp va chạm, như bạn nói. Tuy nhiên, nếu bạn thực hiện một số lượng lớn tra cứu thì độ phức tạp trung bình của mỗi hoạt động là không đổi.

wikipedia Trích dẫn:

phân tích khấu hao khác với hiệu suất trung bình hợp cụ thể trong khả năng mà không có liên quan; phân tích khấu hao đảm bảo thời gian cho mỗi hoạt động trên hiệu suất trường hợp xấu nhất.

Phương pháp này đòi hỏi kiến ​​thức về chuỗi hoạt động nào có thể. Đây là trường hợp phổ biến nhất với cấu trúc dữ liệu, có trạng thái tồn tại giữa các hoạt động. Ý tưởng cơ bản là một hoạt động tồi tệ nhất có thể làm thay đổi trạng thái theo cách mà trường hợp xấu nhất không thể xảy ra một lần nữa trong một thời gian dài, do đó "khấu hao" chi phí của nó.

Answer 8

Không, ký hiệu Big-O không nhất thiết bị giới hạn trong trường hợp xấu nhất. Thông thường bạn sẽ thấy Big-O được xuất bản cho trường hợp tốt nhất, trường hợp trung bình và tệ nhất. Nó chỉ là hầu hết mọi người có xu hướng tập trung vào trường hợp xấu nhất. Ngoại trừ trong trường hợp của một bảng băm trường hợp xấu nhất hiếm khi xảy ra để sử dụng trường hợp trung bình có xu hướng hữu ích hơn.

Có, hàm băm tốt làm giảm xác suất xảy ra xung đột. Hàm băm xấu có thể gây ra hiệu ứng phân cụm (trong đó các giá trị khác nhau băm thành cùng một giá trị hoặc gần với cùng một giá trị). Thật dễ dàng để chứng minh rằng HashSet thực sự có thể trở thành O (n) bằng cách thực hiện hàm GetHashCode theo cách mà nó trả về cùng một giá trị trong toàn bộ thời gian.

Tóm lại, có HashSet và Dictionary có thể được mô tả là có O (1) thời gian chạy phức tạp vì trọng tâm là trên kịch bản trung bình.

Bằng cách này, Big-O cũng có thể được sử dụng để phân tích độ phức tạp được phân bổ. Độ phức tạp phân bổ là cách một chuỗi các hoạt động riêng biệt (và đôi khi thậm chí khác nhau) hoạt động khi nhóm lại với nhau như thể chúng là một hoạt động lớn. Ví dụ, một cây splay được cho là đã phân bổ tìm kiếm, chèn và xóa phức tạp O (log (n)) mặc dù trường hợp xấu nhất cho mỗi O có thể (n) và trường hợp tốt nhất là O (1).

Answer 9

Bảng băm không chỉ có hiệu suất trường trung bình O (1), nhưng nếu hàm băm là ngẫu nhiên, cho bất kỳ phần trăm đã cho nào P < 100%, hiệu suất có thể đạt được P% thời gian từ đúng câu chuyện băm được thiết kế là O (1). Mặc dù các trường hợp ký sinh trùng cực đoan ngày càng trở nên nghiêm trọng hơn khi N tăng lên, điều đó được cân bằng bởi thực tế là thậm chí các trường hợp ký sinh vừa phải trở nên ít hơn và ít có khả năng hơn.