빅오 표기법 (Big-Oh Notation)

알고리즘을 분석하기에 앞서, 기본적인 소스코드를 바탕으로 빅오 표기법을 완성하기까지의 과정을 포스팅하도록 하겠습니다.

 

1. 다음과 같은 소스코드가 주어졌다고 합니다.

 

2. 각 라인을 분석해봅시다.
 'int sum=0' 의 경우 1번

 'for(int i =0; i < _n; i++)' 의 경우 n+1번

 'sum++'의 경우 n번
 따라서 1 + (n+1) + n 이다. 즉, 2n + 2의 결과값을 갖습니다.

 

3. 표기법에 대해서 증명해봅니다.

 2n + 2 <= Cn 일 때, C를 3으로 둡시다. (보통 최상위 차수의 상수값보다 1을 크게 하면 편합니다.)

 2 <= n이 된다. 즉, n이 상수 2 이상의 값을 갖을 때 식이 성립합니다.

 

4. 증명이 되었으니 빅오 표기법 O(n)의 값을 갖습니다.

 

앞으로 모든 소스코드 및 알고리즘의 분석은 위 4개의 과정을 통해 분석하도록 할 것입니다.