알고리즘 평가방법

알고리즘이란 어떤 문제를 해결하기 위한 절차와 방법이다.
이왕 문제를 해결할 거면, 좋은 알고리즘을 쓰면 좋다는데는 이견이 없을 것이다.

그렇다면 좋은 알고리즘은 무엇인가? 어떻게 좋다는 것을 알 수 있을까?
본 글에서는 알고리즘 평가요소, 수학적 알고리즘 평가방법에 대해 끄적여 보겠다.

알고리즘 평가요소

1. 시간의 효율성 : 얼마나 빠르냐?
2. 공간의 효율성 : 얼마나 메모리를 적게 쓰느냐?
3. 코드의 효율성 : 프로그래머 입장에선 가독성, 컴퓨터 입장에선 얼마나 컴파일러와 하드웨어에 최적화 되어 있냐?

3가지 평가요소 중 가장 중요시되는 평가요소는 시간의 효율성이다.
하드웨어가 좋아지면서 공간의 효율성은 비중이 상대적으로 낮아졌으며, 실제로 프로그램이 구동하면서 잡는 메모리를 측정해야하는 어려움이 있다. 코드의 효율성은 프로그래밍 언어에 따라 달라지므로 객관적인 지표가 되기 힘들다.

최선, 평균, 최악의 경우?

모든 알고리즘들은 행복할 떄와 우울할 떄가 있다. 이를 전문용어로 최선의 경우, 최악의 경우라고 한다. 100개의 데이터를 배열에 저장하고, 특정 데이터를 찾는 알고리즘이 있다고 하자.

최선의 경우는 0번쨰 인덱스에서 바로 데이터를 찾는 경우다. 하지만 알고리즘 평가하는데 이는 생각할 필요가 없다. 대부분의 알고리즘은 최선의 경우엔 만족할만한 성능을 보인다.

평균의 경우는, 평균적인 경우를 계산하는게 쉽지 않다. 분석에 필요한 여러가지 시나리오와 현실적인 데이터를 구성해야 하는 문제가 존재한다.

최악의 경우는, 알고리즘 평가방법에 가장 많이 채택되며, 적어도 이정도의 성능은 보장한다 를 보여준다.

알고리즘의 수학적 성능 평가 방법

방법에는 빅-오 표기법, 오메가 표기법, 세타 표기법이 있으며 알고리즘 성능 평가 방법 중 가장 많이 사용하는 방법은 빅-오 표기법이다. 오메가, 세타 표기법에 대해선 다루지 않는다.

빅-오 표기법은 알고리즘 성능을 평가할 때, 최악의 성능을 채택한다. 빅-오 표기법의 수학적 정의는 아래와 같다.

(뜬금없지만, 구글블로그에 수식을 자꾸 넣으려니 화가난다....)
예를 들어 f(n) = 4n^2 + 100 , g(n) = n^2 이라고 하자. f(n) <= Cg(n)을 만족시키면 된다.
만약 C가 100이라면 즉, 4n^2 + 100 <= 100n^2 가 되며, n이 10일 경우 식을 만족하게 된다. 즉 두 개의 상수 C=100, K=10 이 존재하므로 f(n) = 4n^2 + 100의 빅-오는 n^2 이다.

빅-오의 수학적 정의 및 증명에 따라 f(n) = 4n^2 + 100에서 4를 곱하고 100을 더하는 것은 큰 의미가 없다는 말이다. 어떤 시간 복잡도 함수 T(n)이 존재할 때, 빅-오의 연산은 다음과 같다.

T(n) = n^2 + 2n + 1 ==> O(n^2)
T(n) = 999n^3         ==> O(n^3)

빅-오에는 대표적인 표기가 존재하며, 각 표기를 아래 그래프에서 보여준다. 가로축 n은 데이터 갯수 이며, 세로축은 연산횟수의 증가 패턴이다.