hash table 공간 복잡도가 얼마인가요

[익명(220.118)]

ㅈㄱㄴ. ㅈㄱㄴ.

[ELIS(elishaz)]

N

[유카리코(rkdals7979)]

기본적으론 O(1) 인데 너무 많이 차면 rehash 하니까 그런것도 고려하면 O(N) 에 가깝다고 봐야할듯

[kukyakya(143.248)]

아이템을 n개 넣는데 어떻게 공간복잡도가 O(1)이 나오냐 말이 되는 소릴 하셔야죠

[유카리코(rkdals7979)]

복잡도는 1개 넣는다고 O(1)인것이 아님. 100만개를 넣어도 O(1)임

[유카리코(rkdals7979)]

우리가 언제나 아이템의 개수를 알고있는것은 아니기때문에, 해시를 만들때 고정적인 크기를 할당해줌. 여기서 공간복잡도가 O(1)이 나오는것

[유카리코(rkdals7979)]

그러나 해시의 크기가 가득차고 충돌이 많이난다고 추정되면 rehash를 해줘서 크기를 늘림. 근데 이 크기도 사실 처음에 결정한 고정적인 크기를 이용하여 새로운 크기를 만드는거라 O(1)이라 할 수 있음. 근데 아이템의 개수가 커져야 rehash도 되기때문에 아이템의 개수와 해시의 크기가 비례해지는 현상이 생기고, 이것으로 O(N)이라 부르는것임

[kukyakya(180.64)]

이건 뭔 개소리야 해시테이블 버킷에 아이템이 하나만 들어가냐 공간복잡도가 O(1)인 컨테이너 만들면 노벨상감이다

[kukyakya(180.64)]

이건 뭐 big O 개념도 없어보이네

[유카리코(rkdals7979)]

응 맞다. 내가 big O 생각못하고 잘못말했네. 내 말이 잘못됨

[kukyakya(180.64)]

응 나도 말이 좀 심했네 미안