[알고리즘] 시간 복잡도 분류와 점근적 분석

시간 복잡도의 분류

---

시간 복잡도를 쉽개 생각해보자

위의 모토에 따르면, 시간 복잡도는 아래와 같이 3가지로 분류된다.

 

1. 최악 경우 시간 복잡도(worst case)

   모든 입력에 대해서 기본 연산이 수행되는 최대 횟수 

2. 최선 경우 시간 복잡도(best case)

   모든 입력에 대해서 기본 연산이 수행되는 최소 횟수

3. 평균 경우 시간 복잡도(average case)

   모든 입력에 대해서 기본 연산이 수행되는 평균 횟수

 

순차 탐색 알고리즘

예제로 순차 탐색 알고리즘 각 시간 복잡도를 구해보자.

 

1. 최악 경우시간 복잡도(worst case)

   모든 입력에 대해 가장 마지막에 탐색을 성공하는  N

2. 최선 경우 시간 복잡도(best case)

   모든 입력에 대해 가장 첫 번째에 탐색을 성공하는 1

3. 평균 경우 시간 복잡도(average case)

   평균 경우 시간 복잡도는 (최악 시간 복잡도 + 최선 시간 복잡도 / 2) = (N + 1) / 2 번이다.

점근적 분석과 복잡도 함수

---

입력 크기에 따른 시간 복잡도

점근적 분석과 복잡도 함수를 이해하기 위해 위의 그래프를 분석해보자. Input Size가 작을 때는 시간 복잡도 차이가 거의 없다. 그래서 입력이 작을 때는 알고리즘의 효율성이 크게 중요한 항목이 아니다. 하지만, Input SIze가 점점 커짐에 따라 시간 복잡도 차이가 커진다. 그러므로, 입력이 커질 때는 알고리즘을 어떻게 효율적으로 개발하느냐에 따라 알고리즘의 성능이 좌지우지 된다. 

알고리즘의 시간 복잡도를 분석할 때는 입력 크기가 큰 경우를 고려해야 한다. 이를 점근적 분석(Asymptotic Analysis)이라고 한다.

어떤 알고리즘 코드를 점근적 분석하면 복잡도 함수가 도출된다. 코드에서 복잡도 함수를  구할 때는 아래와 같은 3가지 규칙을 따른다.

1. 복잡도는 입력 크기의 N의 함수로 나타낸다.
2. 복잡도 함수는 보통 여러 개의 항을 갖는 다항식이다.
3. 고차 항이 궁긍적으로 시간 복잡도를 지배한다.