다른 검색 데이터 구조의 복잡성에 대해 배우려고합니다. 나는 거의 검색, 삽입 및 삭제를 이해하지만, 내가 얻지 못하는 것은 범위 쿼리이다. 예를 들어, 순서가 지정되지 않은 링크 된 목록 또는 불균형 및 균형있는 빈 트리 (또는 AVL), 또는 해시 테이블의 범위 쿼리 시간 복잡도는 어떻게됩니까? bigocheatsheet.com 사이트를 찾았지만 범위 쿼리에 대해 아무 말도하지 않는 것 같습니다.범위 쿼리 시간 복잡도
기본 검색 및 삽입에 대해서도 해시 테이블이 절반으로 충만하다고 말하면 어떻게 바뀌게됩니까? 완벽한 해시 함수는 상황을 일정하게 만들지 만 완벽하지 않은 경우에는 어떨까요?
범위 쿼리는 주어진 범위 내에 속하는 모든 요소를 찾는 것을 의미합니다. 예를 들어 데이터 구조에서 [a, b]의 범위 쿼리는 a와 b 사이에 속하는 요소의 수를 찾는 것을 의미합니다.
최하위의 경우 전체 목록을 탐색하여 요소 a 및 b를 찾아야하기 때문에 정렬되거나 정렬되지 않은 링크 목록에 대한 범위 쿼리를 제공하려면 O (n) 시간이 필요합니다.
균형이 잡힌 또는 불균형 이진 트리에서 범위 쿼리를 처리하는 경우 트리가 Range Tree이 아닌 한 동일한 최악의 경우 O (n) 시간이 필요합니다. Range Tree이면 range 쿼리는 O (logn, k)를 취합니다. 여기서 k는 해당 범위의 요소 수입니다.
간단히 말해서 범위 쿼리의 시간 복잡성은 데이터 구조가 범위 쿼리를 더 빠르게 만드는 정보로 특별히 증가하지 않는 한 O (n)입니다. 범위 쿼리에 대한 데이터 구조를 최적화하려면 먼저 데이터 집합에서 일부 전처리가 수행되고 필요한 정보가 각 노드에 저장됩니다. 범위 쿼리를 제공 할 때 각 노드에 저장된 정보는 검색 범위를 줄이기 위해 사용됩니다.