검색 알고리즘 - study

알고리즘

• 어떠한 작업을 수행하기 위해
• 우리가 따라야하는 절차 / 스텝
• 얼마나 많은 절차 / 스텝이 존재하는가 => 시간 복잡도

SEARCH 알고리즘

최대한 빠르게, 검색 작업을 수행하는 것

Linear Search

검색을 하기 위한 자연스러운 방법
직선 모양으로 늘어선 배열에서 원하는 키 값을 SEARCH 할때까지 순서대로 검색
처음 부터 끝까지, 순서대로 차근 차근

• 최악의 경우

  • 우리가 찾는 아이템이 배열 맨 마지막에 있거나
  • 배열에 아예 없는 경우

• Linear Time Complexity(선형 시간 복잡도)

• 배열이 커지면 커질수록 선형 검색을 하는 시간도 증가

  • 

Binary Search(이진 검색 알고리즘)

• Sorted Array (정렬된 배열)에서만 사용 가능하다.

• 다만 Sorted Array에서 data가 추가될 경우 / 정렬이 되지 않은 경우보다 시간이 더 오래 걸린다.

  • 아이템을 하나하나 비교한다.
  • 이를 통해 들어갈 위치를 결정한다.
  • 해당 위치의 오른쪽에 있는 모든 값을 이동하여야 한다.

• 이진은 0과 1이 아닌 반으로 쪼갠다는 의미

• 배열의 정중앙에서 시작하여 큰지 작은지 확인하여 이동

• 그렇기 때문에 Sorted Array에서만 시작한다.
  
  

최악의 시나리오로 1만개의 배열이 존재한다면

• Linear Search 는 1만개의 Step을 요구.
• binary Search은 14 스텝이면 완료

정리

1. 대량의 데이터를 검색할때는 Binary Search가 효율적.
2. 다만 Binary Search을 하고싶다면 배열을 정리(Sort)해야 한다.
3. 만약 Sorted Array에 Item이 추가되면 작업 시간이 필요하다.
4. Linear Search는 맨 뒤에 추가만 하면 된다.

선형 검색구현

선형검색의 종료 조건

1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
2. 검색할 값과 같은 요소를 발견한 경우

Linear Search 구현

보초법(sentinel method)

기존 Linear Search는 2개의 조건을 탐색합니다.

if(i == n)
	return -1;
if(a[i] == key)
	return i;

검색값을 배열의 맨 마지막에 넣어 검색을 진행합니다.
아래 조건을 없애 비용을 반으로 줄입니다.

if(i == n)	return -1;

이때 넣는 값을 보초 라고 합니다.

binarySearch 구현

1. a[pc] < key

• a[pl] ~ a[pc] 는 key값보다 작다.
• pl = pc +1로 지정하여 a[pc +1] ~ a[pr]로 지정한다.

2. a[pc] > key

• a[pl] ~ a[pc] 는 key값보다 크다
• pr = pc - 1로 지정하여 a[pl] ~ a[pc-1]로 지정한다.

시간 복잡도(Big O)

• 빠르다, 느리다는 시간으로 판단하지 않는다.
• 같은 알고리즘이더라도 내 컴퓨터보다 동생 컴퓨터가 더 빠르다..(퇴직금으로 컴터사야지)
• 시간은 하드웨어가 결정하기 때문
• 완료까지 걸리는 절차의 수(STEPS)로 결정된다.

O(1)

아래를 살펴보자.

//int[] Array = {1, 2, 3, 4, 5}
void print_First(int[] a)
{
	System.out.println(a[0]);
}

• 배열이 아무리 크더라도 이 함수는 딱 1번이면 실행이 끝남
• 배열이 1만개라도 1번이면 끝
  

  시간 복잡도는 구현에는 신경 쓰지 않는다.
  System.out.print(a[0]); 이 인풋사이즈가 아무리 크던지 Print 문이 100개가 쓰여져 있어도 O(1)로 바라 본다.

O(N)

• Linear Search의 경우
  input size = N / N steps => O(N)
  

//int[] Array = {1, 2, 3, 4, 5}
void print_All(int[] a){
	for(int n : a)
		System.our.println(n);
	for(int n : a)
		System.our.println(n);
}

Quadratic Time(2차시간 / $n^2$)

//int array[][] = {{1, 2, 3}, {1, 2, 3}};
void print_twice_Array(int [][] array){
	for(int i = 0; i < 2; i ++){
    		for(int j = 0; j < 3; j++){
        		System.out.println(array[i][j]);
         	}
        }
}

• 시간 복잡도는 INPUT의 $n^2$
• Input이 10개라면 100개의 스텝이 필요하다.
• Input이 20개라면 400개의 스텝이 필요하다.
• 루프 안의 루프에서 함수를 실행
  

Logarithmic Time(로그시간)

• binary Search
• 반으로 나눈다!