[자료구조] 알고리즘 분석 방법 - Big Oh Notation(빅 오 표기법)

 

 

 

 

 

 

알고리즘이란?

 

: 유한시간 내에 어떤 일을 수행하게 하는 절차. 

 

알고리즘을 수행하기 위해서는 시간과 공간(메모리)가 필요한데, 여기서 시간과 공간은 trade-off하는 관계이다.

즉, 빠른 알고리즘은 보통 메모리를 많이 사용하고, 메모리를 적게 쓰는 알고리즘은 보통 수행시간이 오래걸린다.

 

 

 

 

수행 시간(Running Time)

 

대부분의 알고리즘은 입력을 받아서 오브젝트를 출력한다. 따라서, 입력의 크기에 따라 수행 시간이 달라질 수 있다.

여기서, 평균 수행 시간은 알아내기 어렵기 때문에 최악의 경우(worst case : 아무리 오래 걸려도 이 시간 안에는 해결할 수 있다.)에 가장 집중한다.

최악의 경우를 고려할 경우 분석이 쉽고, 최악의 시간을 고려해야 하는 어플리케이션에 중요하게 작용할 수 있다.

 

 

 

 

 

알고리즘 분석 방법

 

1. 실험적 방법(Experimental Studies)

 

- 직접 구현

- 다양한 개수, 형태의 입력을 넣어봐야 한다.

- clock()과 같은 메소드를 사용해서 실제 수행 시간을 정확하게 측정한다.

 

★ 한계 

① 모든 입력을 실험하지 못했을 수 있다. 

② 해당 알고리즘을 구현하기 어려울 수 있다. 

③ 두 알고리즘을 비교하려면 같은 하드웨어, 소프트웨어 환경에서 비교해야 한다.

 

 

2. 이론적 방법(Theoretical Analysis)

 

- 소스코드로 구현하지 않고, 중요한 부분만 서술한 스도 코드(pseudocode)를 사용한다. 

- 수행 시간을 입력의 크기 n에 대한 함수로 서술한다.

- 모든 가능한 input을 고려할 수 있으며, 하드웨어/소프트웨어에 관계없이 알고리즘의 속도를 측정할 수 있다.

 

 

 

* 방법

① 스도코드 작성

② 기본 연산의 수를 어림잡아 계산하고, n(입력의 크기)에 대한 함수로 작성한다. 

 

 

 

 

수행시간의 증가율

 

최고차항의 차수가 증가율에 영향을 미친다. 

따라서, 기본 연산을 이론적 방법으로 나타냈을 때, 수행시간을 나타내는 함수의 차수가 높을수록 수행시간이 오래 걸린다.

 

예를 들어, 

 

 

 

다음과 같은 경우, f(n)이 g(n)보다 오래 걸리는 알고리즘이라고 할 수 있다.

 

 

하지만, 여기서 상수 팩터는 중요하지 않다. 

이는 n이 어느 정도 커지면 수행시간이 최고차항과 비례해서 증가하기 때문이다!

 

 

 

 

 

다음 그래프를 보면 붉은 선의 최고차항은 1차이고, 보라색 선의 최고차항은 2차이기 때문에, 일정 시점을 지나면, 차수가 큰 값이 증가율이 더 크다고 볼 수 있다.

 

 

여기서 입력값 n은 무한히 커지는 수라고 보기 때문에, 최고차항의 계수가 아무리 크더라도, 차수가 더 큰 알고리즘의 수행시간이 더 오래 걸린다 고 볼 수 있다. 최악의 경우를 보기 때문이다.

 

 

아래 나오는 Big-Oh Notation 역시 이를 바탕으로 한다.

 

 

Big-Oh Notation

 

알고리즘의 입력에 따른 수행시간의 상한으로, 최악의 경우를 고려한다.

빅 오 표기법으로 나타낼 때는, 상수 팩터와 계수는 무시해도 된다. 다시 말해, 최고차항(계수x)만 고려하면 된다는 것이다!

 

 

 

 

두 알고리즘이 다음과 같은 관계에 있다고 할 때, f(n)은 Big-Oh of G(n)이라고 부르며,

 

혹은 

이라고 한다.

 

 

이 경우, f(n)이 아무리 느려도 g(n)의 수행시간보다 클 수 없다는 것을 보여준다.

 

 

 

 

 

 

 

 

 

이 그래프를 다시 한 번 참고하면, 알고리즘의 수행시간을 분석할 때에는 최고차항의 차수만 중요하다고 볼 수 있다.

 

 

그렇다면, 

 

 

과 같은 수식이 모두 성립한다.

 

 

최고차항의 계수와 나머지 요소들을 다 생략하고 표기하는 것이다.