[자료구조/c언어] 시간복잡도

1) 재귀함수의 시간복잡도를 구해보자

int main()
{
	int n;
	scanf("%d", &n); //대입연산 1회
	printf("%d", sum(n)); //연산 cn (c : 더하는 비용)
	return 0;
}

int sum(int x)
{
	if (x <= 0) return 0;
	return x + sum(x - 1);
}

입력 데이터 크기n 에 대한 알고리즘의 수행시간을 T(n)이라고 한다.

상수c는 재귀호출 외에 알고리즘에서 요구하는 처리 비용을 뜻한다. 재귀함수에서는 sum(n-1)과 n을 더하는 비용을 c라고 하자. 

T(n) = T(n-1) +c 이 식을 전개하면

T(n) = T(n-1) +c

 = T(n-2) + 2c 

 = T(n-3) +3c

 = T(n-4) +4c

...

 = T(1) + (n-1)c =< c + (n-1)c = cn 이 과정을 거치면서 T(n) =< cn 이라는 결론을 얻을 수 있다

c는 상수이기 때문에 n만 문자취급을 하고, 점근 표기법으로 나타내면 위의 시간복잡도는 O(n)으로 나타낼 수 있다.