Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

이진 탐색 알고리즘은 수식적으로 표현하기는 부적절하지만 알고리즘의 논리 자체는 재귀적이기 때문에 충분히 가능하다.

이진 탐색 알고리즘은 두 번째 시도 이후부터는 탐색 대상을 찾을 때까지 동일한 패턴을 반복한다. 

때문에 알고리즘 자체는 재귀적인 성격을 지니고 있다. 그래서 재귀적으로 정의가 가능하다. 

# 이진 탐색 알고리즘의 반복 패턴

1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인.

2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작.

# 재귀 함수의 탈출 조건

"탐색 범위의 시작위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우"

이진 탐색 알고리즘을 성능이 떨어지는 재귀함수 기반으로 구현한 이유.

- 재귀함수에 익숙해지기 위함이다.

- 재귀 함수를 기반으로 구현된 위의 이진 탐색 알고리즘도 자연스럽게 이해할 수 있을 정도가 되어야 한다

재귀함수는 이해하는 것도 중요하지만 잘 정의하는 것도 중요하다. 그리고 재귀함수를 잘 정의하기 위해서는 사고의 전환이 필요하다.

# 피보나치 수열: Fibonacci Sequence

수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값

피보나치 수열의 n번째 위치의 값을 반환하는 함수는 수학적으로 다음과 같이 표현이 된다.

int Fib(int n)

{

if(n == 1)

return 0;

else if(n == 2)

return 1;

else

return Fib(n-1)+Fib(n-2);

}

여기서 중요한 것은 수학적 재귀의 표현이 그대로 코드로 옮겨졌으음을 인식하는 것이다.

※ 시간이 지나서 재귀함수에 익수해지면 누구나 함수의 호출순서에 신경을 쓰지 않게 된다.

위에서 보이듯이 피보나치 수열의 7번째 값의 출력을 위해서 25회의 함수호출이 동반되었다. 

때문에 성능상의 불리함은 분명 존재한다.

+ 연산자의 왼편에 있는 Fibo 함수호출이 완료되어야 비로소 + 연산자의 오른편에 있는 Fibo 함수호출이 진행이 된다.

재귀는 자료구조와 알고리즘에 있어서 매우 중요한 요소이고, C언어는 이렇듯 중요한 재귀를 지원하는 언어이다.

재귀함수란, 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다.

"재귀 함수를 실행하는 중간에 다시 재귀 함수가 호출되면, 재귀 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 된다."

실제로 함수를 구성하는 명령문은 CPU로 이동이 되어서(복사가 되어서) 실행이 된다. 그런데 이 명령문은 얼마든지 CPU로 이동이(복사가) 가능하다. 

따라서 재귀 함수의 중간쯤 위치한 명령문을 실행하다가 다시 재귀 함수의 앞 부분에 위치한 명령문을 CPU로 이동시키는 것은 문제가 되지 않는다. 그래서 재귀적인 형태의 함수호출이 가능한 것이다.

위의 코드에서 Recursive 함수에 0이 전달도면서 '재귀의 탈출조건'이 성립되어 함수가 반환하기 시작한다. 

이렇듯 재귀함수의 정의하는데 있어서 탈출조건을 구성하는 것은 매우 중요한 일이다.

재귀함수의 디자인 사례

- 재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 무기이다. 무엇보다도 재귀함수가 있기에 재귀적인 수학적 수식을 그대로 코드로 옮길 수 있다.

# 팩토리얼

위의 식에서 보이듯 f(0)에 해당하는 0!이 1이므로 이것이 재귀함수의 탈출조건이 된다. (수학적으로 0!과 1!은 모두 그 값이 1로 동일하다) 따라서 이제 위의 식은 재귀함수를 이용해서 그대로 코드로 옮길 수 있다.

함수의 코드만 이해하려  하지 말고 그 과정을 이해하려고 노력해야 한다.

순차 탐색 알고리즘의 T(n) 함수:     

이진 탐색 알고리즘의 T(n) 함수:      

                                           →                 

                   →                

※  의 알고리즘을  의 알고리즘으로 개선시키는 것은 약간의 개선이 아닌, 혁신적인 성능의 개선으로 간주된다.

# 비교를 위한 실험의 원칙

- 최악의 경우를 대상으로 비교하는 것이 목적이니 탐색의 실패를 유도한다.

- 탐색의 실패가 결정되기까지 몇 번의 비교연산이 진행되는지를 센다.

- 데이터의 수는 500, 5000, 50000 일 때를 기준으로 각각 실험을 진행한다.

 인 순차 탐색 알고리즘의 경우, 실험을 통하지 않아도 비교연산의 횟수가 500, 5000, 50000 임을 알 수 있다. 선형 빅-오이기 때문에!

두 알고리즘의 비교연산횟수 비교

위의 표에 정리된 결과는  의 알고리즘과  의 알고리즘의 연산횟수에 얼마나 큰 차이가 있는지를 보여준다.

데이터의 수 n과 그에 따른 시간 복잡도 함수 T(n)을 정확히 그리고 오차 없이 구하는 것은 대부분의 경우 쉽지 않다. 

그래서 Big-Oh 표기법을 사용한다.

빅-오라는 것은 함수 T(n) 에서 가장 영향력이 큰 부분이 어딘가를 따지는 것이다. 

이때 사용되는 표기법에 대문자 O, 그러니까 큰 O가 사용되기 때문에 빅-오라고 하는 것이다.

  이것을   이렇게 근사치(approximation) 식을 구성해도 문제가 되지 않는다. 

그 이유는 표를 통해서    에서   이 차지하는 비율을 확인하면 알 수 있다.

 이 차지하는 비율의 증가를 나타내는 표

표에서 보이듯이  이 차지하는 비율은 절대적이다.   이 조금만 증가해도 이내  이 차지하는 비율은 99%를 넘어선다.

따라서,  은  으로 간략화 할 수 있다.

그리고 이것을 빅-오 표기법으로 표현하면 다음과 같다.

         =>            빅-오 오브         =>            

정리하면 함수  의 빅오는  이며, 이는  의 증가 및 감소에 따른  의 변화 정도가  의 형태를 띰을 의미한다.

예를 들면,

                                      ▶                 

                                     ▶                

                    ▶                

그리고 이것을 일반화화면 다음과 같다.

                 ▶                

즉, 다항식으로 표현된 시간 복잡도 함수 T(n)에서 실제로 큰 의미를 갖는 것은  '최고차항의 차수' 라는 이야기다.

※ 빅-오는 "데이터 수의 증가에 따른 연산횟수의 증가 형태(패턴)" 을 나타내는 표기법이다.

 이것은 다음과 같이 이해해야 옳다.

- "데이터 수의 증가에 따른 연산횟수의 증가 형태를 좌표평면상에 그려놓으면, 증가하는 추세가 둔화되는 형태를 띤다. 즉, 로그 그래프와 유사한 형태를 띤다."

빅-오는 성능 분석에 좋은 도구가 된다.

대표적인 빅-오

'데이터 수의 증가'에 따른 '연산횟수의 증가 형태를 표현한 것'이 빅-오이다 보니, 데표적인 빅오 표기가 존재한다. 이것들은 알아둘 필요가 있다.

상수형 빅-오라 한다. 이는 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘이다. 연산횟수가 고정인 유형의 알고리즘을 대표한다.

로그형 빅-오라 한다. 이는 '데이터 수의 증가율'에 비해서 '연산횟수의 증가율' 이 훨씬 낮은 알고리즘을 의미한다. 따라서 매우 바람직한 유형이다. 

참고로 로그의 밑이 얼마냐에 따라서 차이가 나긴 하지만, 그 차이는 알고리즘의 성능관점에서 매우 미미하기 때문에 대부분의 경우에 있어서 무기가 된다.

선형 빅-오라 한다. 이는 데이터의 수와 연산횟수가 비례하는 알고리즘을 의미한다.

선형로그형 빅-오라 한다. 이는 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘을 의미한다. n과 logn을 곱한 형태라서 난해해 보이지만, 알고리즘 중에는 이에 해당하는 알고리즘이 적지 않다.

데이터 수의 제곱에 해당하는 연산홧수를 요구하는 알고리즘을 의미한다. 따라서 데이터의 양이 많은 경우에는 적용하기가 부적절하다.

이는 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 

즉, 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 못하다고 할 수 있다.

데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다.

이는 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 이 역시 그냥 적용하기에는 무리가 있는 알고리즘이다.

지수형 빅-오라 한다. 이는 사용하기에 매우 무리가 있는... 사용한다는 것 자체가 비현실적인 알고리즘이다.

'지수적 증가' 라는, 매우 무서운 연산횟수의 증가를 보이기 때문이다. 처음 알고리즘을 개발했을 때 이러한 성능을 보인다면, 개선의 과정을 거쳐서 현실적인 연산횟수를 보이는 알고리즘으로 수정되어야 한다.

빅-오 표기들의 성능(수행시간, 연산횟수) 의 대소를 정리

   <    <     <     <    <    <  

이진 탐색 알고리즘은 순차 탐색 알고리즘보다 훨씬 좋은 성능을 보이는 알고리즘이다.

하지만 배열을 대상으로 이진 탐색 알고리즘을 적용하기 위해서는 다음의 조건을 만족해야만 한다.

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

즉, 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다 (정렬의 기준 및 방식과는 관계없다).

만약 길이가 9인 배열이 있다고 가정하면...

이진 탐색 알고리즘의 첫 번째 시도:

1. 배열 인덱스의 시작과 끝은 각각 0과 8이다.

2. 0과 8을 합하여 그 결과를 2로 나눈다.

3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다.

즉, 배열의 중앙에, 찾는 값이 저장되어 있는지 확인하는 것이 이진 탐색 알고리즘이다.

이진 탐색 알고리즘의 두 번째 시도:

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

2. 대소의 비교결과는 arr[4] > 3 이므로 탐색의 범위를 인덱스 기준 0~3으로 제한한다.

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

4. 2로 나눠서 얻은 결과가 1이니 arr[1]에 저장된 값이 3인지 확인한다.

두 번째 시도 과정에서 주의 깊게 살펴볼 것은 탐색의 대상을 반으로 줄였다는 사실이다. 이는 어디까지나 배열에 데이터가 정렬된 상태로 저장되었기 때문에 가능한 일이다.이것이 바로 이진 탐색 알고리즘의  핵심이다.

이진 탐색 알고리즘의 세 번째 시도:

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

2. 대소의 비교결과는 arr[1] < 3 이므로 탐색의 범위를 인덱스 기준 2~3으로 제한한다.

3. 2와 3을 더하여 그 결과를 2로 나눈다. 이때 나머지는 버린다.

4. 2로 나눠서 얻은 결과가 2이니 arr[2]에 저장된 값이 3인지 확인한다.

이렇듯 두 번째 시도 이후부터는 탐색 대상을 찾을 때까지 동일한 패턴을 반복할 뿐이다. 하지만 세 번째 시도를 진행하면서 탐색 대상인 3을 찾게 되니, 이로써 탐색은 마무리가 된다.

이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘이다. 때문에 순차 탐색 알고리즘에 비해 좋은 성능을 보인다.

위의 이진 탐색 알고리즘에서 last = mid-1; 과 first = mid+1; 에 감소와 증가가 없다면 어떻게 될까?

값을 하나 빼거나 더해서 그 결과를 변수 last와 first에 저장하지 않으면, mid에 저장된 인덱스 값의 배열요소도 새로운 탐색의 범위에 포함이 된다. 그런데 이는 불필요한 일이다. mid의 배열요소에 탐색 대상이 저장되어 있는지 검사가 이미 끝난 상태이기 때문이다.

그런데 더 큰 문제가 존재한다. 무엇이냐면... 

문제는 탐색의 대상이 배열에 존재하지 않는 경우... 무한루프를 형성하며 프로그램이 종료되지 않는다는 것이다.

탐색의 대상이 배열에 존재하지 않을 경우 first에 저장된 값이 last보다 커져서 반복문을 탈출할 수 있어야 하는데, 위와 같이 코드를 수정하고 나면 결코 first에 저장된 값은 last 보다 커질수 없다 (last는 first보다 작아질 수 없다). 

때문에 무한루프를 형성하게 되는 것이다.

감소나 증가를 하지 않는다면...기본적으로 세 변수에 저장된 인덱스 값은 항상 다음의 식을 만족하도록 알고리즘이 디자인된다.

감소나 증가를 뺀다면, mid에 저장된 값을 가감 없이 first 또는 last에 저장하는 것이 전부이다. 그래서 first는 결코 last보다 커질 수 없고, last는 결코 first보다 작아질 수 없다.

이진 탐색 알고리즘의 시간 복잡도 계산하기 : 최악의 경우(Worst Case)를 기준

우선, 연산횟수를 대표하는 연산이 무엇인지 찾아야 한다.

그런데 이 역시 탐색 알고리즘이니 순차 탐색 알고리즘과 마찬가지로 == 연산을 연산횟수를 대표하는 연산으로 볼 수 있다.

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

- 데이터의 수 n이 n/2, n/4, n/8... 이렇게 줄어서 1이 될 때까지 비교연산을 한 번씩 진행하고, 마지막으로 n이 1일 때 비교연산을 한 번 더 진행한다. 그리고 그것이 탐색 대상이 존재하지 않는 최악의 경우의 비교연산 횟수이다. 그러니까 데이터의 수가 8개였다면 8,4,2,1 이렇게 줄어드니 총 4회 비교연산이 진행된다.

위와 같이 답을 내릴 수 있다. 하지만! 이 정도의 정보는 성능의 분석 및 비교에 사용할 수 없다.

이 정도의 정보를 가지고 앞서 다른 탐색 알고리즘과의 객관적 성능 비교는 가능하지 않다.

위의 데이터의 수가 8개인 상황에서의 비교연산 횟수는 다음과 같이 정리할 수 있다.

# 8이 1이 되기까지 2로 나눈 홧수 3회, 따라서 비교연산 3회 진행.

# 데이터가 1개 남았을 경우, 이때 마지막으로 비교연산 1회 진행.

↓↓↓↓↓ 다시 정리하면...

# n이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교연산 k회 진행.

# 데이터가 1개 남았을 경우, 이때 마지막으로 비교연산 1회 진행.

이로써 비교연산의 횟수를 구했으니, 최악의 경우에 대한 시간 복잡도 함수 T(n)은 다음과 같이 정리된다.

# 최악의 경우에 대한 시간 복잡도 함수 :        T(n) = k + 1

2로 나눈 횟수 k 구하기.

n이 1이 되기까지 2로 나눈 횟수가 k이니, n과 k에 관한 식을 다음과 같이 세울 수 있다.

     =>     n에 8을, k에 3을 대입하면 식은 성립된다. ex) 8 * pow((1/2.0), 3)  하면 1이 나올 것이다. 이 식은 2로 몇 번을 나누어야 1이 되는가에 대한 답을 주는 수식이다.

     ▶         ▶   

※  과 같기 때문에..  이런식이 나올 수 있다.

이제 정리된 최종 수식의 양 변에 밑이 2인 로그를 취한다.

  ▶  ▶   ▶ 

이렇듯 k는 log2n 이다. 따라서 이진 탐색 알고리즘의 최악의 경우에 대한 시간 복잡도 함수 T(n) 은 다음과 같다.

그런데.. 위에 +1이 있었다. 하지만 +1은 중요하지 않다. 

중요한 것은 데이터의 수 n이 증가함에 따라서 비교연산의 횟수가 로그적(logarithmic)으로 증가한다는 사실이다.

"식을 구성하면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있다."

즉, n에 대한 식 T(n)을 구성하는 목적은 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단하는 것이므로 +1은 중요하지 않다.

순차 탐색 알고리즘으로 시간 복잡도 계산

순서 탐색 알고리즘

- 맨 앞에서부터 순서대로 탐색을 진행하는 알고리즘이기에 순차 탐색이라는 이름이 붙어있다.

for(i=0; i<len; i++)

{

if(ar[i] == target)

return i;

}

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

일단, 이 알고리즘에서 사용된 연산자는 <, ++, == 이렇게 세 개이다. 이 연산자들이 얼마나 많이 수행이되는지를 분석하면 되는데...

이 질문에 답을 하고 분석을 진행해야 한다.

"어떠한 연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘인가?"

탐색 알고리즘에서 값의 동등을 비교하는 == 연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이다.

즉, 탐색 알고리즘에서의 핵심은 동등비교를 하는 비교연산에 있다. 비교연산의 수행횟수가 줄어들면 < 연산과 ++ 연산의 수행횟수도 줄어들고, 비교연산의 수행횟수가 늘어나면 < 연산과 ++ 연산의 수행횟수도 늘어나기 때문이다.

정리하면, 다른 연산들은 == 연산에 의존적이다.

따라서 == 연산의 횟수를 대상으로 시간 복잡도를 분석하면 된다. 

이렇듯 알고리즘의 시간 복잡도를 계산하기 위해서는 핵심이 되는 연산이 무엇인지 잘 판단해야 한다. 그리고 그 연산을 중심으로 시간 복잡도를 계산해야 한다.

순차 탐색 알고리즘의 비교 연산횟수를 계산하는데... 순차 탐색 알고리즘은 운이 좋아서 찾고자 하는 값이 배열의 맨 앞에 저장되어 있으면 비교연산의 수행횟수는 1이 되고, 운이 없어서 찾고자 하는 값이 배열의 맨 마지막에 저장되어 있거나 찾고자 하는 값이 아예 저장되어 있지 않으면 비교연산의 수행횟수는 n이 된다. 

이렇듯 모든 알고리즘에는 가장 행복한 경우와 가장 우울한 경우가 각각 존재하며, 이를 전문용어로 '최선의 경우(Best Case)' 그리고 '최악의 경우(Worst Case)' 라 한다. 

그런데 알고리즘을 평가하는데 있어서 '최선의 경우'는 관심대상이 아니다. 어떠한 알고리즘이건 간에 최선의 경우는 대부분 만족할 만한 결과를 보이기 때문이다.

반면, 데이터의 수가 많아지면 '최악의 경우'에 수행하게 되는 연산의 횟수는 알고리즘 별로 큰 차이를 보인다. 따라서 알고리즘의 성능을 판단하는데 있어서 중요한 것은 '최악의 경우'이다.

평균적인 경우(Average Case) 는 시간 복잡도를 평가하는 정보로 의미를 지닌다. 하지만 문제는 이를 계산하는 것이 쉽지 않다는데 있다. 이를 계산하기 위해서는 다양한 이론이 적용되어야 하고, 분석에 필요한 여러 가지 시나리오와 데이터를 현실적이고 합리적으로 구성해야 하는데, 이는 쉽지 않은 일이다.

기본이 되는 다음 질문에 답을 하기조차 쉽지가 않다. 

"무엇이 평균적인 상황인가?"

때문에 '평균적인 경우' 라고 주장하기 위해서는 다양한 자료들이 광범위하게 수집되어야 한다. 결국 일반적인 알고리즘의 평가에는 논란의 소지가 거의 없는 '최악의 경우(Worst Case)' 가 선택될 수 밖에 없다.

순차 탐색 알고리즘의 시간 복잡도 계산하기 : 최악의 경우(Worst Case)

계산할 것이 사실상 없다. 이 알고리즘의 흐름을 소스코드상에서 이해했다면, 다음 사실을 바로 파악할 수 있기 때문이다.

"데이터의 수가 n개일 때, 최악의 경우에 해당하는 연산횟수는(비교연산의 홧수는) n이다."

따라서 순차 탐색 알고리즘의 '데이터 수 n에 대한 연산홧수의 함수 T(n)'은 다음과 같다.

T(n) = n        // 최악의 경우를 대상으로 정의한 함수 T(n)

이처럼 최악의 경우는 생각보다 쉽게, 코드의 분석을 통해서 구할 수 있는 경우도 많다.

순차 탐색 알고리즘의 시간 복잡도 : 평균적인 경우(Average Case)

평균적인 경우의 연산횟수 계산을 위해서 다음과 같이 두 가지를 가정한다.

1. 탐색 대상이 배열에 존재하지 않을 확률을 50%라고 가정한다.

2. 배열의 첫 요소부터 마지막 요소까지, 탐색 대상이 존재할 확률은 동일하다.

탐색 대상이 존재하지 않는 경우의 연산 횟수         n

탐색 대상이 존재하는 경우의 연산 횟수                n/2

그런데 탐색 대상이 배열에 존재하지 않는 경우와 존재하는 경우의 확률이 각각 50%이니 다음과 같이 이 둘을 하나의 식으로 묶어야 한다.

1/2씩 곱해서 더한 이유는 탐색 대상이 존재하지 않을 확률과 존재할 확률이 각각 50%이기 때문이다. 

순차 탐색 알고리즘의 평균적인 경우의 시간 복잡도 함수:     T(n) = 3/4n

※ 최악의 경우에 비해서 상대적으로 시간 복잡도를 구하는 것이 쉽지 않다는 사실에 주목해야 한다. 뿐만 아니라 평균적인 경우의 시간 복잡도 함수는 신뢰도가 높지 않다. 그 이유는 앞서 정의한 두 개의 가정을 뒷받침할 근거가 부족하기 때문이다.

프로그램의 성격에 따라서 그리고 데이터의 성격에 따라서 배열에 탐색 대상이 존재할 확률은 50%보다 높을 수도 있고 높지 않을 수 도 있는데 이러한 부분이 전혀 고려되지 않았다. 

때문에 평균적인 경우의 시간 복잡도는 '최악의 경우'의 시간 복잡도보다 신뢰도가 낮다.

그래서 '최악의 경우'를 시간 복잡도의 기준으로 삼는 이유다!!!

함수그래프그리기.exe