수다닷컴

지금 Thomas H.Cormen의 algorithms 책을 보고 있는데요.

책에서 이해가 안가는 부분이 있어서 아시는 분이 있다면 설명 부탁드려요..

어디 물어볼 곳이 없어서 너무 답답합니다.ㅠ_ㅠ

책 내용을 고대로 적자면...(해시테이블에서 collisinon이 일어날 경우, chaining기법입니다.)

체이닝에 의해 충돌이 해결될 때, 해시 테이블 T내의 dictionary operation들을 구현하는 것은 아주 쉽다.
CHAINED-HASH-Insert (T,x)

리스트 T[h(ket[x])]의 맨 앞에 x를 삽입
CHAINED-HASH-Search (T,k)

리스트 T[h(k)]에서 키 k를 가지는 원소를 검색
CHAINED-HASH-Delete (T,x)

리스트 T[h(key(x)])에서 x를 삭제 왜 searxh에서는 키를 받고, delete나 insert에서는 원소값을 받나요?

무슨 차이가 있는건가요?

...검색 작업의 최악의 경우 수행시간은 리스트 길이에 비례한다. 이 작업에 대한 좀 더 상세한 분석은 아래에서 이루어질 것이다.

리스트가 양방향 연결이 되어 있다면 원소 x의 삭제는 O(1) 안에 이루어질 수 있다

(Chained-Hash-Delete는 입력 인자로 원소 x를 받는 것이지 키 K를 받는 것이 아님을 명심하자.

그러므로 먼저 x를 검색할 필요가 없다. 리스트가 단방향 연결이라면 입력 인자로 키 k보다 원소 x를 갖는 것이 큰 도움이 되는 것은 아니다.

리스트 T[h(key[x])]에서 원소 x를 검색해서 x 직전원소의 next포인터가 x를 뛰어 넘도록 해야 하기 때문이다.

이 경우, 삭제와 검색은 기본적으로 동일한 수행시간을 갖는다).책의 말에 따르면 양방향 연결 시 키값 대신 원소값을 받음으로써 뭔가 도움이 된다는 말인 것 같은데..

뭐가 이득이 되는건지 도무지 모르겠습니다.ㅠ

또 원소 x를 인자값으로 받아도.. 삭제를 하려면 x를 체인으로 연결된 리스트에서 찾아서 없애야 하는 것 아닌가요?

검색은 당연히 해야할 것 같은데...

또 리스트를 따라가다 보면 최악의 경우에는 리스트 길이만큼 수행시간이 결정될 것 같구요.

궁금합니다.ㅠ_ㅠ

아직 배우고 배우는 처지라 쉽고도 명쾌하게 설명을 해 주셨으면 정말 감사할거예요!!!

부탁드립니다....ㅠ

정말 알고리즘 너무 어려워요...

신청하기