1-3 순차 탐색 알고리즘과 이진 탐색 알고리즘

시간 복잡도를 계산 하는데 순차 탐색 알고리즘과 이진 탐색 알고리즘을 사용한다.

 

---

#1 순차 탐색 알고리즘

for(i=0; i<len; i++)
{
	if(ar[i] == target)
    	return i; //찾은 대상의 인덱스 값 반환
}

이 코드는 순차 탐색 알고리즘을 구현한것이다.

이를 토대로 시간 복잡도를 분석해 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구해보자

우선 이 알고리즘에 사용된 연산자는 <, +, ==이렇게 세개다.

이 중에서 == 연산을 적게 수행해야 좋은 알고리즘이다.
이유는 비교연산 == 이 줄어야 < 연산과 ++ 연산의 수행횟수도 줄어들기 때문이다.

다시말해 다른 연산들은 == 연산에 의존적이다

이렇게 알고리즘의 시간 복잡도를 계산하기 위해서는 핵심 연산을 찾아야한다.
그 핵심 연산 중심으로 시간 복잡도를 계산해야한다.

어쨋든 이제 위에 코드로 순차 탐색 알고리즘 느낌을 알 수 있다.
순차 탐색 알고리즘은 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지
차례대로 하나씩 찾아 나가는 것이다

그렇기 때문에 만약 찾고자 하는 값이 맨 앞에 있으면 수행횟수는 1이지만
맨 마지막에 있으면 수행횟수는 데이터의 수 n이 된다.
이 때 각각의 경우를 '최선의 경우', '최악의 경우'라 한다.

알고리즘의 성능을 평가를 할 땐 '평균적인 경우'를 따지는게 좋겠지만
'평균적인 경우'의 조건과 상황을 정확하게 알기는 힘들기 때문에 일반적으로는 '최악의 경우'로 따진다고 한다.

 

이제 최악의 경우를 계산 해보자

'데이터의 수가 n개일 때, 최악의 경우에 해당하는 연산횟수는(== 횟수) n이다'

즉 '데이터 수 n에 대한 연산횟수의 함수 T(n)'은 다음과 같다

T(n) = n

---

#2 이진 탐색 알고리즘

이진 탐색 알고리즘은 다음의 조건을 만족해야만 한다

'배열에 저장된 데이터는 정렬되어 있어야한다'

 

원리는 간단하다

0	1	3	5	14	20	27
index 0	index 1	index 2	index 3	index 4	index 5	index 6

위 표의 정렬된 배열을 arr이라 가정하고

 

이 배열에서 숫자 1이 들어있는지 확인하기 위해

 

이진 탐색 알고리즘을 적용해보자

 

이진 탐색의 첫번째 시도

1, 배열 인덱스의 시작과 끝은 index 0과 index 6이다

2, 0과 6을 합하여 그 결과를 2로 나눈다(절반으로 나누기)

3, 나눈 결과는 3이다

4, 위 배열의 arr[3]에 저장된 값이 1인지 확인한다.

 

그러나 arr[3]은 5였기 때문에 두번째 시도를 한다

1, arr[3]에 저장된 값 5와 탐색 대상인 1의 대소를 비교한다

2, arr[3] > 1이므로 탐색 범위를 arr[3]를 기준으로 인덱스를 0~2로 제한한다

3, 0 + 2를 하여 그 결과를 2로 나눈다. 이때 나머지는 버린다

4, 2로 나눠서 1이 나오므로 arr[1]의 값이 1인지 확인한다

 

두번의 시도로 대상을 찾았다.

확실히 빠르지만 정렬되어 있어야 한다는 조건이 있다.

위의 과정을 반복하는 것이 이진 탐색 알고리즘이다.

절반으로 나눌 때마다 탐색의 대상이 반으로 줄어든다는 특징이 있다.

 

그런데 절반으로 나누다가 시작과 끝의 인덱스가 만나면 어떤 의미일까?

만난다(겹친다)는 아직 탐색의 대상이 하나 남았다는 뜻이다.

 

즉, 두 인덱스가 겹친다 하더라고 탐색이 끝난것은 아니다.

그러므로 기본적인 이진 탐색 알고리즘은 다음과 같은 형태일 것이다.

int first = 0;
int last = len - 1;
int mid;

while(first <= last) //아니면 first < last 이거나 last > first 여야함
{
    int target = 1;
	//이진 탐색 알고리즘 진행
    mid = (first + last) / 2; //탐색 대상의 중앙 인덱스 값
    
    if(target == arr[mid]) //탐색 대상 찾음
        return mid;
    else //못찾으면 다시 반으로 줄이기 
    {
        if(target < arr[mid]) //대소비교
            last = mid - 1;
        else
            first = mid + 1;
    }
}

만나는 인덱스까지 탐색했다는건 탐색에 실패했다는 뜻이기도하다.

 

그런데 코드에서

        if(target < arr[mid]) //대소비교
            last = mid - 1;
        else
            first = mid + 1;

이부분은 왜 mid의 인덱스값이 아닌 -1과 +1을 하였을까?

대소 비교를 하여 대상이 절반 인덱스로부터 왼쪽에 있는지 오른쪽에 있는지 확인을 하면 절반 인덱스는 다음 탐색에서 제외해야한다.

 

절반 인덱스를 제외하지않는다면 무한루프에 걸려 계속 탐색할 것이다.

---

#2 - 1 이진 탐색 알고리즘 최악의 경우의 '시간 복잡도'

 

그렇다면 위의 이진 탐색 알고리즘 코드에서

 

"데이터 수가 n개일 때, 최악의 경우에서 발생하는 비교연산의 횟수는 어떻게 될까?"

 

데이터 수 반으로 줄여 n/2개에서 비교 연산 1번

데이터 수 반으로 줄여 n/4개에서 비교 연산 1번

데이터 수 반으로 줄여 n/8개에서 비교 연산 1번

 

n이 몇개인지 모르기 때문에 정확히 몇번이라고 답하기엔 힘들다.

 

그래서 수학으로 이것을 나타내보도록하자

 

• 8이 1이되기까지 2로 나눈횟수 3회 => 비교연산 3회
• 1인 상태에서 비교연산 한번 더 => 비교연산 1

이것을 일반화시키면

• n이 1이되기까지 2로 나눈횟수 k회 => 비교연산 k회
• 1인 상태에서 비교연산 한번 더 => 비교연산 1

따라서 최악의 경우에 대한 시간 복잡도 함수는 T(n) = k+1 이 된다.

 

그러나 아직 끝이 아니다. 우리는 k를 구해야한다.

 

n을 k회만큼 2로 나누기 때문에 다음과 같이 나타낼 수 있다

이 식을 정리 하면 

이제 로그를 취해보면

최악의 경우에 대한 시간 복잡도 함수는 T(n) = k+1 즉, 위의 식의 k를 대입하면

 

그런데 k+1에서 +1은 어디갔을까?

함수를 구한 이유는 "비교연산의 횟수가 로그적으로 증가한다"는 분석을 얻기 위함이다.

데이터 수가 증가함에 따라 변화의 정도를 분석하기 윈한것이므로 +1은 중요하지않다.