알고리즘이란 어떠한 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정이다. 따라서 서로 다른 알고리즘이여도 결과물은 같을 수 있다.

그렇다면 효율적인 알고리즘을 사용하는것이 좋아보이며 이때 따져 볼 수 있는 것이 시간 복잡도와 공간 복잡도이다.

시간 복잡도

시간 복잡도를 간단히 정의하자면 알고리즘의 시간적인 성능을 의미한다. 즉, 프로세스가 알고리즘을 수행하기위해 해야하는 연산들을 수치화 한것이다.

시간 복잡도의 표현방법에는 다음 3가지 방법이 있다.

• 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
• 평균의 경우 : 세타 표기법 (Big-θ Notation)
• 최악의 경우 : 빅오 표기법 (Big-O Notation)

시간 복잡도는 보통 "빅오 표기법" 으로 판단하여 성능을 예측한다.

빅오 표기법 (Big-O Notation)

시간 복잡도의 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법이다.

<aside>

1 O(1) → 상수

5N + 3, 2N + 10logN O(N) → N이 가장 큰 영향을 미침

5NlogN + 6, NlogN + 30N O(NlogN) → NlogN이 가장 큰 영향을 미침

3N^2, N^2 + 2N O(N^2) → N^2이 가장 큰 영향을 미침

</aside>

<aside>

O(1) : 문제를 해결하는데 오직 한 단계만 처리함.

O(log N) : 문제를 해결하는데 log N 번 만큼의 단계를 처리함.

O(N) : 문제를 해결하는데 N 번 만큼의 단계를 처리함.

O(NlogN) : 문제를 해결하는데 NlogN 번 만큼의 단계를 처리함.

O(N^2) : 문제를 해결하는데 N^2 번 만큼의 단계를 처리함.

</aside>

빅오 표기법의 복잡도를 차트로 나타내면 다음과 같다.

시간 복잡도 구하기

알고리즘의 시간 복잡도는 다음과 같은 유형으로 빠르게 파악할 수 있다.

• 한 개의 루프를 이용해 단일 컬렉션을 반복하는 경우 : O(N)
• 두 개의 다른 루프를 이용해 두 개의 개별 컬렉션을 반복하는 경우 : O(N+M) → O(N)
• 두 개의 중첩 루프를 이용해 단일 컬렉션을 반복하는 경우 : O(N^2)
• 두 개의 중첩 루프를 이용해 두 개의 개별 컬렉션을 반복하는 경우 : O(N*M) → O(N^2)
• 컬렉션의 절반 이상을 반복하는 경우 : O(N/2) → O(N)
• 컬렉션 정렬을 사용하는 경우 : O(Nlog N)

	for (int i = 0; i < N; i++)
	{
		std::cout << i << "\\n";
	}

위의 코드는 N 만큼의 반복문을 수행한다. 따라서 시간 복잡도는 O(N)이다.

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			std::cout << i + j << "\\n";
		}
	}

위의 코드는 N^2 만큼의 반복문을 수행한다. 따라서 시간 복잡도는 O(N^2)이다.

int Fibonacci(int N)
{
	if (N <= 1)
	{
		return N;
	}

	return Fibonacci(N - 1) + Fibonacci(N - 2);
}

위의 코드는 한번 함수를 호출할 때마다 2번씩 재귀로 함수를 호출하기 때문에 2^n 에 비례해서 연산수가 증가한다. 따라서 시간 복잡도는 O(2^N)이다.

값 복사에 따른 시간 복잡도

시간 복잡도를 고려할때는 값 복사에 따른 시간 복잡도도 고려해야한다. C++ 에서 vector 를 함수의 인자로 그대로 넘기면 복사본을 만들어 보내기 때문에 vector 의 크기가 크다면 복사 과정에서 시간이 오래 소요될 것이다.

아래의 코드의 경우 함수의 인자로 vector 를 넘기는 과정에서 값 복사가 일어나며 값 복사이기 때문에 인자로 넘어온 vector 를 변경해도 원본에는 영향을 주지 않는다.

bool Cmp(std::vector<int> v1, std::vector<int> v2, int idx)
{
	return v1[idx] > v2[idx];
}

위 함수는 함수의 인자를 넘기는 과정에서 N 개의 원소를 복사하는 과정 때문에 O(N) 의 시간 복잡도를 갖는다.

만약 C++ 에서 값 복사를 원하지 않는다면 참조자를 이용할 수 있다. 참조자를 통해 함수의 인자를 넘기면 인자를 변경했을때 원본에도 영향이 간다.

bool Cmp(std::vector<int>& v1, std::vector<int>& v2, int idx)
{
	return v1[idx] > v2[idx];
}

위 함수는 원소를 복사하는 과정없이 참조자를 통해 함수의 인자를 넘기기 때문에 O(1) 의 시간 복잡도를 갖는다.

공간 복잡도

공간 복잡도를 간단히 정의하자면 알고리즘의 공간적인 성능을 의미한다.

즉, 프로세스가 알고리즘을 수행하기위해 필요한 메모리 공간을 말한다. 메모리의 기술적인 발전에 따라 최근에는 공간 복잡도보다 시간 복잡도를 중요시하는 트렌드이다.

알고리즘을 실행시키기 위해 필요한 공간은 2 가지로 나눌 수 있다.

• 고정 공간

  알고리즘과 무관한 공간으로 코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간 등이 있다.

• 가변 공간

  알고리즘이 필요로 하는 공간으로 변수를 저장하는 공간, 순환 스택 등이 있다.

공간 복잡도 구하기

공간 복잡도는 "고정 공간 + 가변 공간" 으로 볼 수 있으며 시간 복잡도와 유사하게 빅오 표기법을 사용한다.

int Factorial(int N)
{
	if (N > 1)
	{
		return N * Factorial(N - 1);
	}
	else
	{
		return 1;
	}
}

위 코드의 경우 N 이 1 이하가 될때까지 함수가 재귀적으로 호출되므로 스택에는 N 부터 1 까지 모두 쌓이게 된다. 따라서 공간 복잡도는 O(N) 이다.

int factorial(int N)
{
	int Fac = 1;
	for (int i = 1; i <= N; i++)
	{
		Fac = Fac * i;
	}

	return Fac;
}

위 코드의 경우 N 의 값에 상관없이 스택에는 N 과 i 그리고 Fac 변수만 저장된다. 따라서 공간 복잡도는 O(1) 이다.