1. 자료구조(Data Structure)에 대한 기본적인 이해
자료구조에서는 데이터를 표현하고 저장하는 방법에 대해서 설명한다.
아마도 C언어를 공부하면서 다음과 같은 이야기를 접한 적이 있을 것이다.
"프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것이다."위에서 말하는 '데이터의 표현'은 '데이터의 저장'을 포함하는 개념이다.
그리고 이렇듯 '데이터의 저장'을 담당하는 것이 바로 자료구조이다.
물론 우리는 데이터를 저장한 경험이 있다.
사례를 들면 다음과 같다.
"정수를 저장하기 위해서 int형 변수를 선언한다.""개인정보를 저장하기 위한 목적으로 구조체를 정의한다."넓은 의미에서 int형 변수도, 구조체의 정의도 자료구조에 속한다.
int형 변수도, 구조체도 데이터를 표현 및 저장하는 방법이기 때문이다.
뿐만 아니라 우리는 배열을 선언해서 다양한 정보를 저장한 바 있다.
즉, 배열도 자료구조의 일종이다.
물론 우리가 앞으로 공부할 자료구조는 이렇게 단순하지 않다.
우리는 보다 복잡한 형태의 자료구조들에 대해 이야기할 것이다.
그리고 이러한 자료구조는 기본적으로 다음과 같이 분류할 수 있다.
위 그림에서 보이듯이 파일도 데이터를 저장하는 도구이기 때문에 파일의 구조도 자료구조에 포함이 된다.
하지만 집중적으로 공부할 대상은 '선형 자료구조'와 '비선형 자료구조' 이 두 가지이다.
선형 자료구조는 그 이름이 의미하듯이 자료를 표현 및 저장하는 방식이 선형(linear)이다.
선형이라는 단어의 뜻 그대로 '선의 형태'로 이해하면 된다.
즉, 선형 자료구조는 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식이다.
반면 비선형 자료구조는 그 이름이 의미하듯이, 데이터를 나란히 저장하지 않는 구조이다.
따라서 선형 자료구조에 비해 상대적으로 수월하지 않다.
실무에서는 자료구조를 직접 구현하지 않고 검증된 라이브러리를 가져다 쓴다.
그리고 그것은 합리적인 선택이다.
검증된 라이브러리를 활용하는 것이 안정성에서나 성능 면에서나 우월하기 때문이다.
하지만 라이브러리를 잘 가져다 쓰려면 리스트가 무엇이고 트리가 무엇인지 알아야 한다.
그냥 아는 것이 아니라 각각의 특성을 정확히 이해해야 한다.
친구들의 주소와 전화번호 정보를 저장하기 위한 자료구조를 선택한다고 가정해보자.
이는 리스트로도 가능하고 트리로도 가능하다.
그렇다면 여러분은 무엇을 선택하겠는가?
선택을 하려면 각각의 자료구조를 잘 이해하고 있어야 한다.
선택을 하는데 있어서 자료구조의 구현 능력은 그리 중요하지 않을 수 있다.
"그럼 각종 자료구조를 가져다 쓸 수 있을 정도로만 이해하면 되는 거 아니에요?"전혀 틀린 말은 아니다. 코드 레벨에서 이해하지 않아도, 그림의 형태로 자료구조를 이해하고 설명할 수 있을 정도만 되어도 큰 의미가 있다.
하지만 코드 레벨에서 자료구조를 구현한 경험이 있다면 자료구조를 더 잘 알게 된다.
자료구조를 보는 깊이가 달라진다고 할 수 있다.
뿐만 아니라, 자료구조의 구현 경험은 프로그래밍 능력을 향상시켜 줄 것이다.
혹시 아직 C언어가 익숙하지 않은가?
자료구조를 끝까지 공부하고 나면 C언어에 능통하게 될 것이다.
앞서 말했듯이 자료구조가 '데이터의 표현 및 저장방법'을 뜻한다면, 알고리즘은 이렇듯 표현 및 저장된 데이터를 대상으로 하는 '문제의 해결 방법'을 뜻한다.
예를 들어서 다음의 배열 선언은 자료구조적 측면의 코드이다.
int arr[10] = {1,2,3,4,5,6,7,8,9,10};반면 배열에 저장된 모든 값의 합을 더하는 다음 반복문의 구성은 알고리즘적 측면의 코드이다.
for(idx=0; idx<10; idx++)
sum += arr[idx];위의 반복문은 '배열에 저장된 모든 값의 합을 구하는 알고리즘'이라 할 수 있다.
이렇듯 자료구조와 알고리즘은 밀접한 관계를 갖는다.
자료구조가 결정되어야 그에 따른 효율적인 알고리즘을 결정할 수 있기 때문이다.
만약에 값이 저장된 자료구조가 배열이 아니었어도 위에서 보이는 바와 같이 반복문과 인덱스 값을 이용한 순차적 접근을 진행했을까?
배열이 아니었다면 그 방법은 분명 달라졌을 것이다.
아니 달라져야 한다!
더 타당하고 합리적인 방법으로 말이다.
그럼 다음 문장을 보면서 질문에 답을 해보기 바란다.
"여기 상자가 제법 많이 쌓여 있네요? 이 상자들 중 어딘가에 넣어 둔 머그컵을 찾으셔야 합니다."위의 문장에서 '쌓여있는 상자'는 자료구조이다.
그렇다면 이 상자들을 대상으로 머그컵을 찾는 알고리즘은 어떻게 구성해야 하겠는가?
"딱 봐서 머그컵이 있을법한 상자를 꺼냅니다. 맨 아래에 있는 상자라도 말이죠."위와 같이 답한 사람은 없으리라 믿는다.
상자가 쌓여 있으니 가장 위에 있는 상자부터 순서대로 내려서 찾아봐야 할 것 아닌가?
이제 하고픈 말이 무엇인지 완전히 이해했을 것이다.
"자료구조에 따라서 알고리즘은 달라집니다.""알고리즘은 자료구조에 의존적입니다."때문에 자료구조와 알고리즘은 분명 다른 과목임에도 불구하고 매우 많은 연관성을 지니고 있다.
그래서 앞으로는 자료구조를 설명하고 그와 관련이 있는 알고리즘도 더불어 소개할 것이다.
2. 알고리즘의 성능분석 방법
알고리즘을 평가하는 두 가지 요소는 다음과 같다.
"어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느리냐?""어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰냐?"이렇듯 하나는 '속도'에 관한 것이고 다른 하나는 '메모리의 사용량'에 관한 것인데, 속도에 해당하는 알고리즘의 수행시간 분석결과를 가리켜 '시간 복잡도(time complexity)'라 하고, 메모리 사용량에 대한 분석결과를 가리켜 '공간 복잡도(space complexity)'라 한다.
사실 메모리를 적게 쓰고 속도도 빨라야 최적의 알고리즘이라 할 수 있다.
그런데 일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행속도에 초점을 둔다.
대게는 속도에 관심이 더 많고, 또 중요한 요소로 판단되기 때문이다.
그럼 어떻게 속도를 평가할 수 있을까?
시계를 가져다 놓고 수행시간을 재면 되는 것일까?
혹 시간을 잴 수 있어도 큰 의미를 부여하기는 어렵다.
처리해야 할 데이터양의 변화에 따른 속도의 증가 및 감소의 정도도 알아야 하는데, 이를 위해서 조건을 달리하여 수백 번, 수천 번 샐행해가면서 시간을 잴 수는 없는 일이기 때문이다.
그래서 알고리즘의 수행속도를 평가할 때는 다음과 같은 방식을 취한다.
"연산의 횟수를 셉니다""그리고 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성합니다."말 그대로 연산의 횟수를 통해서 알고리즘의 빠르기를 판단한다.
물론 연산의 횟수가 적어야 빠른 알고리즘이다.
그리고 '데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성한다'는 것은 데이터의 수를 함수에 입력하면 연산의 횟수가 바로 계산이 되는 식을 구성한다는 뜻인데, 이렇듯 식을 구성하는 이유는 다음과 같다.
"식을 구성하면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있습니다."즉 알고리즘 별 연산횟수를 함수 T(n)의 형태로 구성하면, 다음 그림에서 보이는 바와 같이 그래프를 통해서 데이터 수의 변화에 따른 연산횟수의 변화 정도를 한눈에 파악할 수 있으며, 이로 인해서 둘 이상의 알고리즘을 비교하기가 용이해진다.
위 그림에서 보이는 것이, 동일한 기능을 제공하는 서로 다른 두 알고리즘의 성능을 비교한 결과라고 가정하고, 이 두 알고리즘의 비교결과를 나열해 보겠다.
"데이터의 수가 적으면 알고리즘 B가 더 빨라!""근데 데이터의 수가 좀 늘어나면 알고리즘 A가 더 빨라지는데?"위의 분석결과를 토대로 다음과 같이 판단할 수도 있다.
"데이터의 수가 적은 경우에는 알고리즘 B를 적용하고, 데이터의 수가 많은 경우에는 알고리즘 A를 적용해야 한다."뭐 잘못된 판단은 아니다.
나름 합리적인 판단이고 실제로 이렇게 판단하고 실제로 이렇게 판단하고 적용하기도 하니 말이다.
하지만 데이터의 수가 적은 경우, 속도 차가 나봐야 얼마나 나겠는가?
중요한 것은 데이터의 수가 많아짐에 따른 연산횟수의 증가 정도에 있다.
"그렇게 놓고 보면 알고리즘 A가 훨씬 좋은 알고리즘이네요!"그렇다! 알고리즘 A가 훨씬 좋은 알고리즘이다.
"그럼 알고리즘 B는 필요없겠네요?"큰일 날 소리다!
대게 A와 같이 안정적인 성능을 보장하는 알고리즘은 B와 같은 성격의 알고리즘에 비해서 구현의 난이도가 높은 편이다.
따라서 데이터의 수가 많지 않고 성능에 덜 민감한 경우라면 구현의 편의를 이유로 B와 같은 알고리즘을 선택하기도 한다.
결론적으로 알고리즘은, 종합적으로 사고하고 판단하여 상황에 맞게 구현을 해야 한다.
그럼 이번에는 '순차 탐색 알고리즘'이라는 매우 간단한 탐색 알고리즘 하나를 소개하고 이를 대상으로 시간 복잡도를 계산해 보고자 한다.
#include <stdio.h>
#include <string.h>
int LSearch(int arr[], int len, int target) // 순차 탐색 알고리즘 적용된 함수
{
int i;
for(i=0; i<len; i++)
{
if(arr[i]==target)
return i; // 찾은 대상의 인덱스 값 반환
}
return -1; // 찾지 못했음을 의미하는 값 -1 반환
}
int main(void)
{
int arr[9]={3,6,5,8,2,4,1,9,7};
int idx;
idx=LSearch(arr, sizeof(arr)/sizeof(int), 9);
if(idx==-1)
puts("탐색 실패");
else
printf("타겟 인덱스: %d", idx);
return 0;
}이제 위의 코드를 토대로 시간 복잡도를 분석해서 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구해보자.
"이 알고리즘에서 사용된 연산자는 <, ++, == 이렇게 세 개네요, 얘네들이 얼마나 많이 수행되는지를 분석하면 되는거죠?"물론 연산횟수를 세라고 하였으니 모든 연산자를 대상으로 연산횟수를 세어야 할 것 같은 느낌이 들 수 있다.
그렇다면 다음 질문에 답을 해보자
"어떠한 연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이겠는가?"답을 하였는가? 그렇다!
값의 동등을 비교하는 == 연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이다.
즉, 탐색 알고리즘에서의 핵심은 동등비교를 하는 비교연산에 있다.
비교연산의 수행횟수가 줄어들면 < 연산과 ++ 연산의 수행횟수도 줄어들고, 비교연산의 수행횟수가 늘어나면 < 연산과 ++ 연산의 수행횟수도 늘어나기 때문이다.
정리하면, 다른 연산들은 == 연산에 의존적이다.
따라서 우리는 == 연산의 횟수를 대상으로 시간 복잡도를 분석하면 된다.
이렇듯 알고리즘의 시간 복잡도를 계산하기 위해서는 핵심이 되는 연산이 무엇인지를 잘 판단해야 한다.
그리고 그 연산을 중심으로 시간 복잡도를 계산해야 한다.
"알고리즘마다 핵심이 되는 연산을 찾는 것도 쉬운 일은 아닐 것 같은데요?"맞다! 사실 객관적인 근거를 마련해서 알고리즘의 성능을 분석하는 것 자체가 쉬운 일이 아니다.
그러나 흔히 하는 일은 아니니 부담을 갖지는 말자.
그럼 다시 본론으로 돌아와서 순차 탐색 알고리즘의 비교연산 횟수를 계산해보자.
그런데 순차 탐색 알고리즘을 봐서 알겠지만, 운이 좋아서 찾고자 하는 값이 배열의 맨 앞에 저장되어 있으면 비교연산의 수행횟수는 1이 되고, 운이 없어서 찾고자 하는 값이 배열의 맨 마지막에 저장되어 있으면 비교 연산의 수행횟수는 n이 된다.
이렇듯 모든 알고리즘에는 가장 행복한 경우와 가장 우울한 경우가 각각 존재하며, 이를 전문용어로 '최선의 경우(best case)' 그리고 '최악의 경우(worst case)'라 한다.
그런데 알고리즘을 평가하는데 있어서 '최선의 경우'는 관심대상이 아니다.
어떠한 알고리즘이건 간에 최선의 경우는 대부분 만족할만한 결과를 보이기 때문이다.
반면 앞서 본 그래프를 통해서도 수 있듯이, 데이터의 수가 많아지면 '최악의 경우'에 수행하게 되는 연산의 횟수는 알고리즘 별로 큰 차이를 보인다.
따라서 알고리즘의 성능을 판단하는데 있어서 중요한 것은 '최악의 경우'이다.
그런데 이렇게 되물어 볼 수도 있다.
"최악도 최선도 아닌 평균적인 경우를 따져야 하는 것 아닌가요?"정확한 지적이다!
실제로 '평균적인 경우(average case)'는 시간 복잡도를 평가하는 정보로 의미를 지닌다.
하지만 문제는 이를 계산하는 것이 쉽지 않다는데 있다.
이를 계산하기 위해서는 다양한 이론이 적용되어야 하고, 분석에 필요한 여러 가지 시나리오와 데이터를 현실적이고 합리적으로 구성해야 하는데, 이는 쉽지 않은 일이다.
간단히 말해서 기본이 되는 다음 질문에 답을 하기조차 쉽지 않다.
"대체 무엇이 평균적인 상황인가?"때문에 '평균적인 경우'라고 주장하기 위해서는 다양한 자료들이 광범위하게 수집되어야 한다.
결국 일반적인 알고리즘의 평가에는 논란의 소지가 거의 없는 '최악의 경우(worst case)'가 선택될 수밖에 없다.
그럼 순차 탐색 알고리즘의 시간 복잡도를 계산해보겠다.
그런데 계산할 것이 사실상 없다.
이 알고리즘의 흐름을 소스코드 상에서 이해했다면, 다음 사실을 바로 파악할 수 있기 때문이다.
"데이터의 수가 n개일 때, 최악의 경우에 해당하는 연산횟수는(비교연산의 횟수는) n이다."따라서 순차 탐색 알고리즘의 '데이터 수 n에 대한 연산횟수의 함수 T(n)'은 다음과 같다.
이번에는 앞서 설명한 순차 탐색보다 훨씬 좋은 성능을 보이는 이진 탐색 알고리즘을 소개하고자 한다.
하지만 배열을 대상으로 이진 탐색 알고리즘을 적용하기 위해서는 다음의 조건을 만족해야만 한다.
"배열의 저장된 데이터는 정렬되어 있어야 합니다."즉, 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다.
때문에 이진 탐색 알고리즘보다 성능이 덜한 순차 탐색 알고리즘도 우리에겐 유용한 알고리즘이다.
그럼 이진 탐색 알고리즘의 원리를 설명하고 그 다음에 이를 적용한 예제를 소개하겠다.
우선 길이가 9인 배열에 다음과 같이 정렬된 상태로 데이터가 저장되어 있다고 가정하자.
위 그림의 배열 이름을 arr이라고 가정하고, 이 배열을 대상으로 숫자 3이 저장되어 있는지 확인하기 위해서 이진 탐색 알고리즘을 적용해 보겠다.
그럼 시작해보자.
이진 탐색 알고리즘의 첫 번째 시도
1. 배열 인덱스의 시작과 끝은 각각 0과 8이다.
2. 0과 8을 합하여 그 결과를 2로 나눈다.
3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다.즉, 다음 그림과 같이 배열의 중앙에, 찾는 값이 저장되어 있는지 확인하는 것이 이진 탐색 알고리즘의 첫 번재 시도이다.
첫 번째 시도를 통해서 arr[4]에 3이 저장되지 않았음을 확인하였으니 두 번째 시도를 진행할 차례다.
이진 탐색 알고리즘의 두 번째 시도는 다음과 같이 진행이 된다.
이진 탐색 알고리즘의 두 번째 시도
1. arr[4]에 저장된 값 9와 탐색 대상인 3의 대소를 배교한다.
2. 대소의 배교결과는 arr[4]>3이므로 탐색의 범위를 인덱스 기준 0~3으로 제한한다.
3. 0과 3을 더하여 그 결과를 2로 나눈다. 이때 나머지는 버린다.
4. 2로 나눠서 얻은 결과가 1이니 arr[1]에 저장된 값이 3인지 확인한다.두 번째 시도 과정에서 주의 깊게 살펴볼 것은 탐색의 대상을 반으로 줄였다는 사실이다.
이는 어디까지나 배열에 데이터가 정렬된 상태로 저장되었기 때문에 가능한 일이며, 이것이 바로 이진 탐색 알고리즘의 핵심이다!
두 번째 시도 내용을 그림으로 정리하면 다음과 같다.
이 표에서 색이 바랜 부분은 탐색의 대상에서 제외되었음을 의미한다.
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을 찾게 되니, 이로써 탐색은 마무리가 된다.
마지막으로 진행이 된 세 번째 시도의 내용을 그림으로 정리하면 다음과 같다.
자! 그럼 이진 탐색 알고리즘을 기반으로 한, 총 3회의 탐색과정에서 탐색 대상의 범위가 어떻게 줄었는지 그림을 통해 정리하겠다.
이렇듯 이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘이다.
때문에 앞서 소개한 순차 탐색 알고리즘에 비해 좋은 성능을 보인다.
이제 이진 탐색 알고리즘의 구현을 보이고자 한다.
참고로 이진 탐색 알고리즘은 개념적으로 매우 간단하고 또 구현을 위해서 많은 양의 코드를 필요로 하지는 않지만 구현 시 신경 쓸 부분이 없지는 않다.
그럼 구현에 앞서 탐색의 범위가 줄어드는 형태를 다음 그림을 통해서 다시 한 번 관찰하자.
위 그림에서는 탐색의 시작위치에 해당하는 인덱스 값을 first, 탐색의 마지막 위치에 해당하는 인덱스 값을 last로 표시하고 있다.
이 그림에서 보이는 바와 같이 이진 탐색 알고리즘이 진행됨에 따라서 first와 last는 가까워진다.
그 거리를 반씩 줄여가며 가까워진다.
그렇다면 이진 탐색 알고리즘은 언제까지 계속되어야 하겠는가?
"first와 last가 만날 때까지요! first와 last가 만나면 탐색의 대상이 존재하지 않음을 뜻하니 탐색의 과정을 종료해야 합니다."이는 그럴듯한 답변 같지만 잘못된 답변이다!
first와 last가 만났다는 것은 탐색의 대상이 아직 하나 남아있음을 뜻하기 때문이다.
다라서 이진 탐색은 first < last 인 상황에서는 물론이거니와 first == last인 상황에서도 계속되어야 한다.
때문에 이진 탐색 알고리즘은 다음과 같은 형태로 반복문이 구성된다.
while(first <= last)
{
...
}그리고 이는 다음의 결론으로 자연스럽게 이어진다.
first가 last보다 큰 경우 탐색은 종료된다.
그리고 이렇게 종료가 되었다는 것은 탐색에 실패했음을 뜻한다.
그럼 지금까지 한 이야기를 토대로 이진 탐색 알고리즘을 구현해보겠다.
이 예제에서 정의하고 있는 BSearch 함수가 이진 탐색 알고리즘의 구현에 해당된다.
#include <stdio.h>
int BSearch(int arr[], int len, int target)
{
int first=0; // 탐색 대상의 시작 인덱스 값
int last=len-1; // 탐색 대상의 마지막 인덱스 값
int mid;
while(first<=last)
{
mid=(first+last)/2; // 탐색 대상의 중앙을 찾는다.
if(arr[mid]==target) // 중앙에 저장된 값이 타겟이라면
return mid; // 탐색 완료!
else // 타겟이 아니라면
{
if(target<arr[mid])
last=mid-1;
else
first=mid+1;
}
}
return -1; // 찾지 못하면 -1 반환
}
int main(void)
{
int arr[5]={1,3,5,7,9};
int idx;
idx=BSearch(arr, sizeof(arr)/sizeof(int), 9);
if(idx==-1)
puts("탐색 실패");
else
printf("타겟 인덱스: %d", idx);
return 0;
}위 코드를 보면 mid의 배열요소에서 타겟을 찾지 못했을 경우 mid에서 1을 빼거나 더한 값을 first나 last에 넣어준다.
첫 번째 이유는 당연하게도 이미 mid인덱스 값과 taget을 비교했기 때문에 굳이 한 번 더 비교할 필요가 없기 때문이다.
두 번째 이유는 탐색을 하다가 무한 루프가 형성될 수 있기 때문이다.
예를 들어, first가 1이고 last가 2일 경우 mid값이 1이므로 arr[1]과 target을 비교하게 되는데, arr[1]이 target값이랑 다를 경우 target이 arr[1]보다 큰 상황이므로 first에 1을 넣게 된다.
그렇게 되면 또 다음 비교연산에도 arr[1]과 target을 비교하게 되므로 무한 루프가 형성되는 것이다.
이 두 가지 이유 때문에 mid에서 1을 빼거나 더한 값을 first나 last에 넣어주는 것이다.
이진 탐색 알고리즘도 순차 탐색 알고리즘과 마찬가지로 == 연산이 연산회수를 대표하는 연산으로 볼 수 있다.
그럼 다음 질문에 직접 답을 해보자.
"데이터의 수가 n개일 때, 최악의 경우에 발생하는 비교연산의 횟수는 어떻게 되는가?"답이 딱 나오는가?
사실 답이 딱 나오지는 않는다.
그렇게 간단히 나오지 않기 때문이다.
이진 탐색 알고리즘의 비교연산의 횟수는 딱 떨어지게 말을 할 수는 없다.
그리고 이것이 이진 탐색 알고리즘의 시간 복잡도 계산에 대한 어려움이다.
그럼 한번 데이터의 수가 n개일 때 비교연산은 총 몇 회가 진행되는지 세어보자
이는 데이터의 수 n을 대상으로 다음과 같이 일반화할 수 있다.
- n이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교연산 k회 진행
- 데이터가 1개 남았을 때, 이때 마지막으로 비교연산 1회 진행이로써 비교연산의 횟수를 구하였으니, 최악의 경우에 대한 시간 복잡도 함수 은 다음과 같이 정리가 된다.
물론 이것이 끝이 아니다.
k를 구하는 문제가 남아 있다.
그런데 이 1이 되기까지 2로 나눈 횟수가 이니, 과 에 관한 식을 다음과 같이 세울 수 있다.
이제 위의 식을 에 관한 식으로 나타내기 위해서 다음과 같이 정리해야 한다.
↓
↓
이제 남은 일은, 정리된 최종 수식의 양 변에 밑이 2인 로그를 취하는 것이다.
그럼 식은 다음과 같이 정리가 된다.
↓
↓
↓
이렇듯 는 이다.
따라서 이진 탐색 알고리즘의 최악의 경우에 대한 시간 복잡도 함수 은 다음과 같다.
+1은 데이터의 수 이 증가함에 따라서 연산횟수의 변화 정도에 큰 영향을 끼치지 않기 때문에 중요하지 않다.
사실 데이터의 수 과 그에 따른 시간 복잡도 함수 을 정확히 그리고 오차 없이 구하는 것은 대부분의 경우 쉽지 않다.
그래서 대부분 빅-오만 따진다.
빅-오라는 것은 함수 에서 가장 영향력이 큰 부분이 어딘가를 따지는 것인데, 이때 사용되는 표기법에 대문자 O, 그러니까 큰 가 사용되기 때문에 빅-오라고 하는 것이다.
빅-오에 대한 설명을 위해서 다음 시간 복잡도 함수를 보자.
이는 다음과 같이 간략화, 조금 더 수학적으로 표현하면 근사치 식을 구성해도 문제가 되지 않음에 동의할 것이다.
그렇다면 다음과 같이 간략화를 한차례 더 진행해도 무리가 없을까?
이러한 상황에서 다음과 같이 생각하는 것은 매우 당연하다.
"과감하게 2n을 빼버렸네! 2n을 그냥 빼도 되는 거 맞아? 지나친 거 아니야?"그럼 다음 표를 통해서 에서 2n이 차지하는 비율을 확인해 보자.
그럼 2n을 빼도 되는지 나름의 판단이 설 것이다.
표에서 보이듯이 이 차지하는 비율은 절대적이다.
이 조금만 증가해도 이내 이 차지하는 비율은 99%를 넘어선다.
이렇듯 다음 식에서,
이 미치는 영향은 미미해지므로 다음과 같이 간략화 할 수 있다.
그리고 이를 빅-오 표기법으로 표현하면 다음과 같다.
정리하면 함수 의 빅오는 이며, 이는 의 증가 및 감소에 따른 의 변화 정도가 의 형태를 띔을 의미한다.
그렇다면 수식을 보고서 빅-오를 구하는 방법은 무엇일까?
수학적인 접근 없이도 다음 사실을 알면 어렵지 않게 빅-오를 구할 수 있다.
"T(n)이 다항식으로 표현이 된 경우, `최고차항의 차수`가 빅-오가 된다."그리고 이를 일반화하면 다음과 같다.
이렇듯 '데이터 수의 증가'에 따른 '연산횟수의 증가 형태를 표현한 것'이 빅-오이다 보니, 대표적인 빅-오 표기가 다음과 같이 존재하니 이를 알아둘 필요가 있다.
이를 상수형 빅-오라 한다.
이는 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘을 뜻한다.
예를 들어서 연산의 횟수가 데이터 수에 상관없이 3회 진행되는 알고리즘일지라도 이라 하지 않고 이라 한다.
이렇듯 에는 연산횟수가 고정인 유형의 알고리즘을 대표한다는 의미가 담겨 있다.
이를 로그형 빅-오라 한다.
이는 '데이터 수의 증가율'에 비해서 '연산횟수의 증가율'이 훨씬 낮은 알고리즘을 의미한다.
따라서 매우 바람직한 유형이다.
참고로 로그의 밑이 얼마냐에 따라서 차이가 나긴하지만, 그 차이는 알고리즘 성능관점에서 매우 미미하기 때문에 대부분의 경우에 있어서 무시가 된다.
이를 선형 빅-오라 한다.
이는 데이터의 수와 연산횟수가 비례하는 알고리즘을 의미한다.
이를 선형로그형 빅-오라 한다.
이는 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘을 의미한다.
과 을 곱합 형태라서 난해해 보이지만, 알고리즘 중에는 이에 해당하는 알고리즘이 적지 않다.
이는 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다.
따라서 데이터의 양이 많은 경우에는 적용하기가 부적절한데, 이는 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다.
달리 말하면 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 못하다고 할 수 있다.
데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다.
이는 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다.
이 역시 그냥 적용하기에는 무리가 있는 알고리즘이다.
이를 지수형 빅-오라 한다.
이는 사용하기에 매우 무리가 있는, 사용한다는 것 자체가 비현실적인 알고리즘이다.
'지수적 증가'라는 매우 무서운 연산횟수의 증가를 보이기 때문이다.
처음 알고리즘을 개바했을 때 이러한 성능을 보인다면, 개선의 과정을 거쳐서 현실적인 연산횟수를 보이는 알고리즘으로 수정되어야 한다.
지금까지 설명한 빅-오 표기들의 성능(수행시간, 연산횟수)을 그래프로 정리하면 위와 같다.
우리가 앞서 공부한 두 탐색 알고리즘의 빅-오를 판단하는 시간을 갖겠다.
이를 위해서 두 탐색 알고리즘의 함수를 살펴보자.
지금까지 설명한 내용을 잘 이해했다면 특별한 설명 없이도 각각의 빅-오 표기는 다음과 같음을 알 것이다.
사실 큰 차이가 없다고 느낄 수도 있다.
하지만 잘못된 생각이다.
의 알고리즘을 의 알고리즘으로 개선시키는 것은 약간의 개선이 아닌, 혁신적인 성능의 개선으로 간주되기 때문이다.
이에 대한 이해를 위해서 과 의 성능을 보이는 두 알고리즘의 비교연산횟수를 수치적으로 비교해보겠다.
위의 표에 정리된 결과는 의 알고리즘과 의 알고리즘의 연산횟수에 얼마나 큰 차이가 있는지를 보여준다.
