시간 복잡도, 공간 복잡도

시간 복잡도

• 프로그램을 실행해서 종료까지 걸리는 시간, 컴파일타임 + 실행시간
• 입력된 N의 크기에 따라 실행되는 조작의 수를 나타냄

연산 시간 크기 순서

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

코드를 통한 시간 복잡도 분석

int sum(int A[], int n)
{
	int s, i;
	s = 0;
	for (i = 0; i < n; i++)
	{
		s = s + A[i];
	}
	return s;
}

s=0 //할당은 1
for loop문은 i=0인 1+ n번 반복 => n+1
s=s+A[i]는 n번 반복하므로 n
return s // 1
f(n)=2n+3 , 시간복잡도:O(n)

void Add(int n)
{
	int i, j;
	for (i = 0; i < n; i++) //n+1
	{
		for (j = 0; j < n; j++) //n(n+1)
		{
			C[i][j] = A[i][j] + B[i][j];//n^2
		}
	}
}

• 외부 loop문은 전 코드와 마찬가지로 n+1이다. 그런데, 내부 loop문은 n번 반복하는데 nested loop라서 n(n+1)이다
• matrix는 n*n = n^2
  따라서 f(n)=2n^2+2n+1, O(n^2)

📢함수 내부에서 함수를 호출할 때 맹목적으로 O(1)이라고 하면 안되고, 내부 함수의 정의를 보고 판단해야 된다. 즉, 내부 함수에 loop가 있는지 없는지 따져봐야 한다.