Developer Ahn

- sequential search

- 정렬여부 상관없이 비슷한 성능

- 시간복잡도: 

- 개선된 순차 탐색
 : 비교 횟수를 줄이는 방법

int seq_search2(int key, int low, int high) 
{
    int i;
    list[high+1] = key;
    for(i=low; list[i] != key; i++) // 키 값을 찾으면 종료
        ;
    if(i==(high+1)) return -1; //탐색 실패
    else return i;             //탐색 성공
}

- 키 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)

- 해시 테이블을 이용한 탐색을 해싱(hashing)

- dictionary = map = table

- 해시 함수(hash function)란 탐색 키를 입력으로 받아 해시 주소(hash address)를 생성하고 이 해시 주소가 배열로 구현된 해시 테이블(hash table)의 인덱스가 된다.

 

- 탐색 키 k1가 k2에 대하여 h(k1) = h(k2)인 경우를 충돌(collision)이라고 하며, 이러한 키들을 동의어(synonym)라고한다. -> 충돌은 곧 오버플로(overflow)

- 해시 함수
  : 충돌이 적어야 한다.
  : 해시 함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포되어야 한다.
  : 계산이 빨라야 한다.
  : 제산 함수(mod 연산), 폴딩 함수, 중간 제곱 함수 등
  : 충돌 해결 방법으로 선형 조사법, 이차 조사법, 이중 해싱법, 체이닝 등

- topological sort

- 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

- 진입 차수가 0인 정점을 선택하고, 선택된 정점과 여기에 부속된 모든 간선을 삭제 -> 반복

- 사이클이 있는 경우 위상정렬 불가