HashSet 조회 복잡성?

단일 작업에 대한 검색 작업 또는 은 최악의 경우에 O(n) 일 수 있습니까? 따라서 n 요소의 경우 hashSet에서 조회하면 O(n^2)이됩니까?HashSet 조회 복잡성?

2011-07-04 phoenix

"for n elements"는 정확히 무엇을 의미합니까? 각 요소에 대한 조회를 수행 하시겠습니까? 최악의 경우는 O (n)이지만 일반적으로 O (1)입니다. –

예 O이 필요하지만 정말 최악의 경우의 다음 HashSet의 모든 요소는, 같은 해시 코드를가 (또는 해시 코드로 이어지는 경우 같은 양동이). hashCode과 올바르게 분배 된 키 샘플을 사용하면 조회는 O (1)입니다.

2011-07-04 18:27:39

-18

lookp는 (C)

는 C = 상수 값

2011-07-04 18:27:05

예,하지만 우리가 HashSets를 사용하는 이유는 매우 낮은 확률로이 최악의 경우가 발생한다는 것입니다. 일반적으로 힙 또는 자체 분산 TreeSet에 대해 보장 된 nlogn보다 훨씬 빠릅니다. 정렬되지 않은 목록에 대해 n^2를 보장합니다.

2011-07-04 19:08:50 krasnerocalypse

답변