다차원 해시의 공간 복잡도

Question

C1, C2, C3 및 C4가 데이터의 열을 나타내고 N 개의 데이터 행이있는 경우 탭으로 구분 된 값의 입력을 저장하고 싶습니다. 그렇다면 해시에서 조회를 수행하여 C1, C2, C3, C4에 대한 특정 값이 존재하는지 확인할 수 있습니다. 누군가 나에게 최악의 경우,이 공간의 복잡도가 N 이라고 제안했습니다. 왜 그것이 사실이 아닌지에 대한 명확한 설명을 공식화하는 데 도움이되고 싶습니다.

Answer 1

다른 사람은 N × N 격자의 점을 저장하려고하면 N 포인트가 저장 될 것이라고 생각하고 있습니다.

하지만 N 포인트가 있다면 해시를 저장하는 것입니다. 그리고 N 개의 데이터 포인트가있는 해시는 일반적으로 O (N) 개의 공간을 필요로합니다. (기술적으로 해시 테이블의 크기와 데이터의 공간을 차지하지만 해시 테이블의 크기를 데이터 집합과 크기가 같은 순서로 동적으로 조정합니다.)