03-1 검색 알고리즘
검색과 키
그 주목하는 항목을 키(key)라고 하겠습니다.
배열에서 검색
1. 선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색을 수행합니다.
2. 이직 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행합니다.
3. 해시법: 추가 , 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행합니다.
체인법: 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
오픈 주소법: 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법
03-2 선형 검색 linear search sequential search
요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때 까지 맨앞부터 순서대로
요소를 검색하는 것
static int seqSearch(int[] a, int n , int key){
int i = 0
while(true){
if(i == n)
return -1;
if (a[i] == key)
return i;
i++;
}
}
int[] x = new int[num];
무한 루프의 구현
while(true){ } |
for(;;){ } |
do{ } |
보초 sentinel method
이 비용을 반으로 줄이는 방법
static int seqSearch(int[] a, int n , int key){
int i = 0
a[n] = key;
while(true){
if (a[i] == key)
break;
i++;
}
return i == n ? -1 : i ;
}
int[] x = new int[num+1];
03-3 이진검색 binary search
요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘입니다.
맨 앞 인데스를 pl , 맨 끝 인덱슬르 pr, 중앙 인덱스를 pc
초기화 pl = 0, pr = n-1, pc = (n-1)/2
1. a[pc] < key
a[pl] ~ a[pc]는 제외 , 검색 범위는 중앙요소 a[pc]보다 뒤쪽의 a[pc+1] ~ a[pr]
pl값을 pc+1로 업데이트 한다.
2. a[pc] > key
a[pc] ~ a[pr]는 제외 , 검색 범위는 중앙요소 a[pc]보다 뒤쪽의 a[pl] ~ a[pc-1]
pr값을 pc-1로 업데이트 한다.
이진 검색은 검색을 반복할 때 마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의
평균값은 log n이다.
이진 검색 알고리즘은 검색 대상(배열)되어 있음을 가정합니다.
static int binSearch(int[] a, int n , int key){
int pl = 0
int pr = n-1;
do{
int pc = (pl+pr)/2;
if (a[pc] == key)
return pc;
else if(a[pc] < key)
pl = pc+1;
else
pr = pc -1
}while(pl <= pr);
return -1;
}
복잡도
알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도 (complexity)라고 합니다.
1. 시간 복잡도 time complexity: 실행에 필요한 시간을 평가하는 것
2. 공간 복잡도 space complexity : 기억 영역과 파일 공간이 얼마나 필요한가를 평가 하는 것
선형 검색의 시간 복잡도 O(n)
평균 실행 횟수는 n/2입니다.
이진 검색의 시간 복잡도
static int binSearch(int[] a, int n , int key){
int pl = 0
int pr = n-1;
do{
int pc = (pl+pr)/2;
if (a[pc] == key)
return pc;
else if(a[pc] < key)
pl = pc+1;
else
pr = pc -1
}while(pl <= pr);
return -1;
}=>O(log n)
Arrays.binarySearch에 의한 이진 검색
binarySearch
장점 1 . 이진 검색 메소드를 직접 코딩할 필요가 없다.
장점 2 . 모든 자료형 배열에서 검색 할 수 있다.
검색에 성공한 경우 : key와 일치하는 요소의 인덱스를 반환
검색에 실패한 경우 x라고 할 떄 -x-1
기본 자료형 배열에서 binarySearch메소드로 검색하기
클래스 메서드와 인트턴스 메서드
인스턴스 메서드 (비정적 메서드) static붙이지 않고 선언한 메소드
클래스 메서드(정적 메서드) static 을 붙여 선언한 메소드
둘의 차이점은 메서드가 인스턴스에 포함되는지'의 여부에 있습니다.
자연 정렬 : 사람에게는 오른쪽 형태의 정렬이 더 자연스럽습니다. 바로 이 정렬을 자연 정렬 이라고 한다.
파라미터 이름 작성 :
1. 1개의 대문자를 사용합니다.(소문자는 가급적 사용하지 않습니다.)
2. 컬렉션의 자료형은 element의 앞글자인 E를 사용합니다.
3. 맵의 키 , 값은 key와 value의 앞글자인 K와 V를 사용합니다.
4. 일반적으로는 T를 사용합니다.
출처 : Do it ! 자료구조와 함께 배우는 알고리즘 입문 자바편