[ 개발 잡소리 ] 시간 복잡도 (Time Compleity)

시간복잡도란

알고리즘의 성능을 분석, 평가할 때 사용하는 방법의 일종이다

 

알고리즘의 성능을 분석하는 방법은 여러 가지가 있는데

 

1. 진짜로 실행시켜서 걸린시간을 측정하는 방법이 있고

2. 알고리즘의 복잡도를 분석하여 알아낼 수도 있다

 

알고리즘의 복잡도를 분석하는 방법은

직접 코드를 실행시키지 않고도 분석이 가능하고

알고리즘에서 수행되는 연산의 횟수를 측정하여 비교한다

 

이 알고리즘의 복잡도에는 두가지의 내부 개념들이 추가로 있는데

바로 공간 복잡도와 시간 복잡도이다

 

공간복잡도는 코드 실행 시 필요로 하는 메모리 공간을 분석하는 부분이고

시간복잡도는 코드 실행 시간을 분석하는 부분이다

 

수행시간은 여러 경우에 해당하는 입력에 대한 기본연산들의 횟수이다

* 기본 연산 (산술, 대입, 비교, 이동)

 

대충 3가지가 있는데

최선, 최악, 평균의 경우가 있다

 

---

시간복잡도를 표기할 때는 보통

"빅오" 표기법을 사용하여 표기하는데

 

이는 연산 횟수가 다항식으로 표현될 때,

가장 값이 빠르게 증가하는 최고차항을 제외한 모든 항과 최고차항의 계수를 제외하여 나타낸다

 

예시)

최고차항만 나타내기 : 

   Func(n) = n² + 7n + 4 = O(n²)

 계수 떼내기 :

   Func(n) = 5n = O(n)

 

이런 식으로 사용하면 된다

 

void Func(int n) {
	for (int i = 1; i <= n; i++)
	{ //n
		for (int j = 1; j <= 5; j++)
		{ // n * 5
			for (int k = 1; k <= n; k++)
			{ // n * 5 * n
				cout << "ming";
			}
		}
	}
}

이 코드를 빅오표기법으로 표기하면

O(n²) 이다