[알고리즘] 시간 복잡도, 점근적 분석법 그리고 표기법

1.  시간 복잡도 시간 복잡도 (Time complexity)는 컴퓨터 공학에서 사용되는 알고리즘을 입력의 크기에 관계해서 나타내는 방법이다.  

 왜 절대 시간을 쓰지 않을까? 절대시간은 사실 컴퓨터 환경 의존성이 심하다. 예를 들어, A 알고리즘은 B 컴퓨터에서 1초동안 100개의 입력을 처리할 수 있지만, C 컴퓨터에서는 10개만 해결할 수 있다면, 이 알고리즘에 대한 절대적 평가가 힘들 수 있다.

 따라서 절대 시간이 아닌, 입력의 크기 n에 따라서 알고리즘 동작까지 필요한 시간을 n에 대한 수식으로 나타내는 것이다.

 

  2. Basic Operation 시간 복잡도를 나타낼 때, 측정하는 단위이다. "기본연산"이라고도 하며, 입력의 크기에 비례해서 나타내는 경향을 보인다. 예를 들어 아래의 코드를 실행한다고 생각하자.

for (int i = 0; i < n; i++){ // basic operation i
  array[i] *= 10;  // basic operation array[i]
}

 위의 함수는 입력받은 n개의 정수형 데이터에 10을 곱하는 동작을 한다. 여기서 변수 i와 array는 입력 크기 n에 비례하여, 곱셈과 덧셈이라는 basic operation을 수행하게 된다.

 Basic Operation은 사실 관점에 따라서 기준이 바뀔 수 있다. 예를 들어 산술 연산( +, -, *, /, %)만 포함하는 경우가 있으며, 비트 연산 그리고 대입 연산까지 포함하는 경우도 있다.

 

  3. 시간 복잡도 표기법 위와 같이 시간복잡도를 표기하는 방법을 정의하기 앞서 알고리즘이 가지는 불확실성에 대해서 고려해야 한다.

 만약 가장 작은 숫자를 찾는 문제를 생각해보자. n개의 입력에서 가장 작은 숫자가 어디 포함될 지 컴퓨터가 예상할 수 있을까?

inputs1 = { 1, 5, 2, 3, 7 } // best case
inputs2 = { 2, 3, 1, 3, 9 } // average case
inputs3 = { 9, 8, 7, 4, 1 } // worst case

이 처럼 우리는 세가지 경우로 나누어 생각해야 한다.

1. 최선의 경우 (대부분 첫 시행에 찾아진다.)
2. 평균의 경우 (최선과 최악의 산술 평균 값이다.)
3. 최악의 경우 (대부분 맨 마지막 경우에 찾아진다.)

 만약 입력의 크기 n=100,000,000이라면, 최선의 경우에는 1번만에, 최악의 경우에는 n번만에 찾을 것이다. 따라서 이러한 조건들을 표기하기 위하여, 총 3개의 표기법을 제공한다.

1. Omega Notation
2. Theta Notation
3. Big O Notation

 

4. 시간 복잡표 표기법 상세

(1) Omega Notation

오메가 표기법은 충분히 큰 n개의 입력에 대하여, 시간 복잡도 함수가 f(x)일 때,

`g(x) <= f(x)`

를 만족하는 함수를 말한다.

 예를 들어 f(x)가 3n+2 라고하자, 이 함수는 항상 g(x) = n보다 크다. 따라서 Omega(n) 이라고 표기한다.

 

(2) Theta Noation

세타 표기법은  충분히 큰 n개의 입력에 대하여, 시간 복잡도 함수가 f(x) 일 때,

`g1(x) <= f(x) <= g2(x)`

를 만족하는 함수를 말한다.

 예를 들어 f(x)가 3n+2 라고하자, 이 함수는 항상 g1(x) = n보다 크고, g2(x)=10*n보다 작다. 따라서 Theta(n) 이라고 표기한다.

 

(3) Big O Notation

빅 오 표기법은  충분히 큰 n개의 입력에 대하여, 시간 복잡도 함수가 f(x) 일 때,

`f(x) <= g(x)`

를 만족하는 함수를 말한다.

 예를 들어 f(x)가 3n+2 라고하자, 이 함수는 g(x)=10*n보다 작다. 따라서 O(n) 이라고 표기한다.

 사실 이 포스트에 내용은 굉장히 축약되어 있는 편이다. 따라서 어떠하다 정도만 이해하고, 위키피디아를 참고하여 보충하길 바란다.