빅오 표기법(Big-O notation), 시간복잡도, 공간복잡도

해당 글은 공부를 하면서 적은 글이기 때문에 틀릴 수 있습니다. 참고용으로만 봐주세요~

이전부터 알고리즘이나 자료구조를 공부하면서 Big-O표기법과 시간 복잡도 등에 대해 궁금해서 알아보았던 것을 정리해보자.

빅오 표기법(Big-O notation)

Big-O 표기법은 인수가 특정 값 또는 무한대로 향하는 경향이 있을 때 함수의 동작을 설명하는 수학적 표기법이다.

이러한 Big-O 표기법은 프로그래밍에 관련해서 크기가 커짐에 따라 실행시간 또는 공간 요구사항이 증가하는 방식에 따라 알고리즘을 분류하는데 사용된다. 즉, Big-O 표기법은 프로그래밍에서 시간복잡도와 공간복잡도를 설명할 때 이용된다.

 

어떤 양수 n0가, c가 존재할 때 f(n)은 O(g(n))이다. 이때 n0와 c는 다음을 만족해야 한다.

n0 이상의 모든 n에 대해 f(n) <= cg(n)

 

이해가 잘 안되서 좀 더 생각을 해보니, 어떤 함수 f(n)을 O(g(n))으로 나타낼 때, n0 즉, 특정 값보다 이상인 값이 들어가면, 무조건 f(n)보다 cg(n)이 크기 때문에 식에 붙어있는 계수(coefficient)는 아무 상관이 없다는 것이다.

때문에 상수는 무시하고 O(g(n))으로 표기한다는 의미인 것 같다.

 

O(n^2+n)은 O(n^2)과도 같다.

왜냐하면 n^2가 커지는 정도가 n이 커지는 정도보다 크기 떄문에 언젠가는 n^2의 영향력이 n의 영향력을 묻어버리기 때문이다.

따라서 덧셈으로 구분되는 여러 항 중에서는 가장 크게 증가하는 식 하나만 남겨두면 된다.

그러나 O(n^2+m)같이 각 항의 변수가 다를 경우 함부로 없앨 수 없다.

왜냐하면, m이 n^2보다 클 수 있기 때문에 종속성이 없는 경우 함부로 없애서는 안된다.

 

자주쓰이는 Big-O 표기법을 분류하면 다음과 같다.

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) ...

오른쪽으로 갈 수록 값이 커진다.

 

시간 복잡도

시간 복잡도는 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼만큼 걸리는가?이다.

효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 것이다.

즉, 같은 결과를 도출해내는 서로다른 알고리즘 중 어떤 알고리즘을 사용해야 시간을 적게 써서 효율적이게 프로그래밍을 할 수 있냐는 것이다. (입력값이 작을 경우 크게 의미 없지만, 입력값이 커지면 커질수록 차이는 명확해진다.)

이러한 시간 복잡도는 주로 Big-O표기법을 사용해 나타낸다.

 

시간 복잡도를 표기하는 방법에는 크게 3가지가 있다.

• Big-O(빅-오)  -> 상한 점근 (즉, 최악)
• Big-Ω(빅-오메가) -> 하한 점근 (즉, 최선)
• Big-θ(빅-세타) -> 그 둘의 평균 (즉, 평균)

이중 Big-O 표기법을 사용하는 이유는 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.

(이는 우리가 프로그래밍을 할때 해당 로직을 사용하면, 이 정도 시간까지 걸릴 수 있다.를 고려해야하기 때문이다. 컴퓨터의 연산속도가 빠르기 때문에 입력값이 작을 때는 왠만한 알고리즘을 이용해도 소요시간은 비슷하지만, 입력값이 커지면 커질 수록 소요시간이 커지기 때문에 최악의 시간을 생각해가며 프로그래밍을 하는게 좋기 때문이라고 생각한다.)

 

시간 복잡도에서 자주 사용되는 Big-O 표기법의 종류

위에서도 적었던 해당 Big-O표기법의 종류를 살펴보려한다.

O(1)

일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. (즉, 상수 시간)

O(1)의 시간 복잡도를 가진 알고리즘

int O1_algorithm(int arr[5], int index)
{
	return arr[index];
}

int main()
{
	int MyArr[5] = {1, 2, 3, 4, 5};
	int index = 1;

	int result = O1_algorithm(MyArr, index);

	return 0;
}

이 알고리즘에서는 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있다.

예를 들어 MyArr의 길이가 100만이어도, 즉시 해당 index에 접근해 값을 반환할 수 있다.
(물론 배열 길이가 길어지면, 함수 인자도 변경되어야 말이 맞다.)

 

Stack에서 push와 pop이 이에 해당된다.

 

O(n)

선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

예를 들어 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있다.

O(n)의 시간 복잡도를 가진 알고리즘

#include <iostream>

using namespace std;

void O_n_algorithm(int n)
{
	for (int i = 0; i < n; ++i)
	{
		cout << i;
	}
}

void another_O_n_algorithm(int n)
{
	for (int i = 0; i < 2 * n; ++i)
	{
		cout << i;
	}
}

해당 함수는 입력값(n)이 1증가할 때마다 i를 출력해준다.

즉, n이 증가할 때마다 함수 완료 시간이 같은 비율로 증가하므로 O(n)이다.

두 번째 함수는 O(2n)이지만, 입력값이 커질 수록 계수인 2는 영향력이 적어지기 때문에 O(n)으로 표기한다.

 

O(log n)

로그 복잡도(logarithmic complexity)라고 부르며, Big-O 표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

O(log n)의 시간 복잡도를 가지는 알고리즘은 BST(Binary Search Tree)가 있다.

BST 알고리즘은 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절만들어 줄어든다.

(BST에 관해서는 이후에 포스팅할 것이다.)

 

O(n log n)

퀵 정렬, 병합 정렬, 힙정렬이 이에 해당한다.

 

O(n^2)

2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

O(n^2)의 시간 복잡도를 가진 알고리즘

#include <iostream>

using namespace std;

void O_quadratic_algorithm(int n)
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			cout << i;
		}
	}
}

2중 for문이기 때문에 n이 1이면 1회 반복하고, n이 2면 4번, 3이면 9번 반복하게된다.

이렇게 n이 증가함에 따라 걸리는 시간도 제곱 만큼 증가하게 된다.

 

또한 비효율 적인 정렬인 버블 정렬과 삽입 정렬 및 선택정렬도 이에 해당한다.

 

O(C^n), O(2^n)

기하급수적 복잡도(exponetial complexity)라고 부르며, Big-O 표기법중 가장 느린 시간 복잡도를 가진다.

O(2^n)의 시간 복잡도를 가진 알고리즘

가장 대표적인 알고리즘은 피보나치 수열을 재귀로 구현한 함수이다.

 

공간 복잡도

공간 복잡도는 프로그램을 실행시킨 후 완료하는데 필요한 리소스 공간의 양이다.

총 공간 요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며 수식으로는 S(P)=c+Sp(n) 으로 표기한다.

고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말한다.

가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간을 말한다. 즉, 동적으로 필요한 공간을 의미한다.

 

공간 복잡도 예제 코드

int main()
{
	int N, X, A[1000];
	cin >> N >> X;
	for (int i = 0; i < N; ++i)
	{
		cin >> A[i];
	}
	for (int i = 0; i < N; ++i)
	{
		if (A[i] < X)
		{
			cout << A[i];
		}
	}
	return 0;
}

위 코드는 입력 받은 N만큼 반복 수행하기 때문에 시간복잡도가 O(n)이라는 것을 쉽게 알 수 있다.

N개의 수를 받아 배열에 저장해야하기 때문에 공간복잡도는 O(n)이 된다.

int main()
{
	int N, X;
	cin >> N >> X;
	for (int i = 0; i < N; ++i)
	{
		int A;
		cin >> A;
		if (A < X)
		{
			cout << A;
		}
	}
	return 0;
}

이 코드의 경우 배열 A에 대한 메모리는 전혀 따로 보유하지 않고서 문제를 풀 수 있기 때문에 공간 복잡도는 O(1)이다.

 

참고 블로그 및 자료

 

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

 

시간복잡도와 공간복잡도(Time Complexity Space Complexity)