[Section 1] 알고리즘의 분석 _ 성장률(Rate of Growth)

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

알고리즘에 따라서 데이터의 처리 속도가 달라질 수 있으며, 이는 상황에 따라서 또 다르다. 이번에는 알고리즘의 분석방법에 대해 알아보기 위해 프로그래밍에서 언급하는 성장률에 대해 이해해보자. 

1.  알고리즘 분석에 중요한 성장률

알고리즘 분석에서 쉽게 오해할 수 있는 사항을 나열하면 다음과 같다.

 

• 알고리즘 분석에 좋은 지표는 바로 프로그램의 시간 측정이다.
• 알고리즘 분석에 좋은 지표는 바로 수행 명령의 총량이다. 
• 어떤 문제든지 이상적인 단 하나의 알고리즘이 존재한다.

 

첫 번째 문장은 프로그램의 동작 시간이 컴퓨터의 성능에 따라 달라질 수 있으므로 항상 좋은 지표는 아니다. 그리고 수행 명령이 많아진다고 해서 꼭 나쁜 알고리즘은 아니다. 이것은 프로그래머의 코딩 습관에 의존하기 때문이다. 마지막으로 알고리즘은 상황에 따라서 맞는 알고리즘이 존재하며, 데이터의 숫자에 따라서도 시간 복잡도가 달라진다. 그렇다면, 알고리즘 분석에 꼭 필요한 것은 무엇일까? 바로 성장률(Rate of Growth)이다.

 

알고리즘 분석에 있어 성장률은 알고리즘의 수행 속도를 지칭하는 용어이다. 알고리즘의 수행 속도는 데이터의 전체 수와  연산 횟수에 영향을 미치기 때문에 수행 시간에 따른 시간 복잡도를 계산하기 위해서는 성장률을 비교해야 한다. 다시 말해서, 성장률은 데이터의 수 에 따라 변화하는 총 연산 횟수를 나타낸다고 할 수 있다. 다음의 표는 알고리즘 분석에서 자주 사용되는 성장률의 시간 복잡도를 나타내고 있다.

 

시간 복잡도와 성장률 형태	함수 이름	설명
1	상수	시간 복잡도가 상수인 형태로 단순한 덧셈 혹은 뺄셈 연산의 시간복잡도이다.
log n	로그	시간 복잡도가 로그 함수 꼴이다.
n	선형	시간 복잡도가 선형 함수 꼴이다.
n log n	선형 로그	시간복잡도가 선형 로그 함수 꼴이다.
n2	2차	시간복잡도가 2차 함수 꼴이다.
n3	3차	시간복잡도가 3차 함수 꼴이다.
2n	지수	시간복잡도가 지수 함수 꼴이다.

 

* 위에서 아래의 순서로 성장률이 커진다. 

2.  알고리즘의 성장률 예측 _ 최고 성장률

알고리즘의 시간 복잡도를 예측할 때에도 이 성장률을 기준으로 판단한다.  예를 들어 다음의 함수가 존재한다고 가정하자. 

 

"f(n) = 2n² + 4n +2"

 

데이터의 개수가 많고, 알고리즘이 복잡할 때 모든 경우를 고려하여 시간 복잡도를 계산하기는 어려운 일이다. 따라서 우리는 가장 높은 시간 복잡도를 가지는 항, 2n² 을 기준으로 시간 복잡도를 예측한다. 그리고 이것을 최고 성장률(highest rate of growth)이라 부른다.

 

최고 성장률 예시

3.  분석의 세 가지 유형 _ 최악, 최고, 그리고 평균 상태

알고리즘 분석에는 최악, 최고, 그리고 평균 상태가 존재한다. 말 그대로 알고리즘은 시간 복잡도를 기준으로 하여 최고 상태와 최악의 상태로 나눈다. 이해를 돕기 위해 다음의 예시를 보자. 

 

"f(n) = n² +2"

 

입력된 함수의 최고 성장률만 따진다는 것이 알고리즘의 일반적 분석 방법이다. 예를 들어, f(n)을 어떤 알고리즘의 시간 복잡도라고 가정해보자. 이 알고리즘은 n개의 입력값에 따라 시간 복잡도가 주어진 함수 형태로 증가할 것이다. 따라서 우리는 이 프로그램의 동작에 걸리는 시간을 느리게 할 수도, 빠르게 할 수 도 있다. 먼저 주어진 알고리즘을 최대한 느리게 동작하게 하려면 n개의 입력값(엄청나게 큰 수)을 넣으면 된다. 

 

* 알고리즘의 분석은 데이터의 개수에 따라 점근적(asymptotic) 분석을 한다. 

 

최고의 상태는 알고리즘을 빠르게 동작하게 하는 입력값 n개 일 때의 함수를 의미한다. 마지막으로 최고, 최악의 상태의 사이에 해당하는 n개의 데이터를 입력하는 경우를 평균 상태(Average Case)라 칭한다. 결과적으로 알고리즘의 분석은 데이터 개수에 의존하는 것이다. 다음의 수식을 참고하자.

 

알고리즘의 분석 방법

 

최고, 최악의 상태를 명확히 이해하려면 상한과 하한의 개념에 대해 알아야 한다. 이는 이후의 빅-오, 빅-오메가 표기법에서 다루고자 한다.

 

 

* 다음 강의는 빅-오 표기법입니다.

[Section 1] 알고리즘의 분석 _ 빅-오 표기법