[알고리즘] 시간 복잡도와 점근 표기법

Intro

AI에게 썸네일을 만들어달라고 시켜보았다.

 

알고리즘 문제를 풀다보면 자주 등장하는 것이 시간 복잡도이다.

이 글에서는 알고리즘의 시간 복잡도의 정의와 이를 표현하는 방법인 점근 표기법에 대해 서술한다.

 

알고리즘의 성능을 어떻게 판단할까?

크게 정확도와 효율성으로 판단할 수 있다.

그 중 효율성은 시간 효율성과 공간 효율성으로 나뉜다.

 

시간 효율성을 나타낼 때는 시간 복잡도를 사용하고,

공간 효율성을 나타낼 때는 공간 복잡도를 사용한다.

 

하지만 대개 공간복잡도의 상한은 시간복잡도이기 때문에 시간복잡도를 많이 사용한다.

 

시간 복잡도의 정의

시간복잡도 = 알고리즘을 실행하는데 걸리는 시간을 표현하는 것

 

CS(컴퓨터과학/공학) 분야에서 시간복잡도란 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다.

 

알고리즘으로 한정해서 이야기를 한다면

알고리즘이 실행되는데 걸리는 시간을 입력 크기로 나타내는 것을 말한다.

 

그렇다면 시간복잡도는 어떻게 표현할까?

시간복잡도는 대개 점근 표기법 중 Big-O 표기법을 사용한다.

점근 표기법의 정의

점근 표기법에는 크게 3가지 종류가 있다.

Big-O 표기법 ( 점근적 상한 표기법 )

$O(g(n))=$  최악의 경우에 $g(n)$ 만큼 소요된다.

Big-O 표기법은 $O(g(n))$ 으로 표현한다.

 

함수 $f(n)=O(g(n))$ 이라고 하자.

함수  $f$ 의 증가 속도가 함수 $g(n)$보다 더 빠르지 않다는 것을 보장한다.

즉, 함수 $f$ 는 아무리 빨리 증가해도 $g(n)$ 보다 느리게 증가한다.

쉽게 말해 최악의 경우 $g(n)$ 이다.

 

수학적으로 조건은 다음과 같다.

 

만약 어떤 $c$가 0 보다 크고, 어떤 자연수 $n_0$ 가 존재할 때,

모든 $n\ge n_0$ 인 상황에서,  $f(n)\le cg(n)$ 가 성립한다면

$f(n)$은 $g(n)$ 보다 더 빠르게 증가하지 않는다.

즉, $f(n)=O(g(n))$ 이다.

 

예시로 다음과 같은 함수가 있다고 생각해보자

$f(n)=n^5+2n^3+19n$

그렇다면 Big-O 표기법의 정의에 의해

$f(n)=O(n^5)$

$f(n)=O(n^7)$

이라고 할 수 있다.

그러나,

$n^5$ 는 $n^3$ 보다는 빠르게 증가하기 때문에,

$f(n)\ne O(n^3)$ 이다.

 

CS 분야에서 시간복잡도나 공간복잡도를 의미하면 대부분 Big-O 노테이션으로 표기한다.

 

Omega 표기법 ( 점근적 하한 표기법 )

 $\Omega (g(n))=$ 최소한 $g(n)$ 만큼 소요된다.

Omega 표기법은 $\Omega (g(n))$ 으로 표현한다.

 

함수 $f(n)=\Omega (g(n))$ 이라고 하자.

함수  $f$ 의 증가 속도가 함수 $g(n)$보다 더 빠르게 증가하거나, 최소한 같은 속도로 증가한다는 것을 의미한다.

쉽게 말해, 최선의 경우 $g(n)$ 만큼 걸린다는 것을 말한다.

 

수학적으로 설명하면 다음과 같다.

만약 어떤 $c$가 0 보다 크고, 어떤 자연수 $n_0$ 가 존재할 때,

모든 $n\ge n_0$ 인 상황에서,  $f(n)\ge cg(n)$ 가 성립한다면

$f(n)$은 $g(n)$ 보다 더 느리게 증가하지 않는다. 

즉, $f(n)=\Omega (g(n))$ 이다.

 

Theta 표기법 ( 점근적 평균 표기법 )

$\Theta (g(n))=g(n)$과 동등하게 증가한다. 

Theta 표기법은 $\Theta (g(n))$으로 나타낸다.

 

함수 $f(n)=\Theta (g(n))$ 이라고 하자.

함수  $f$ 의 증가 속도가 함수 $g(n)$와 정확히 같은 증가 속도를 나타낸다는 것을 의미한다.

 

수학적 조건은 다음과 같다.

만약 $f(n)=O(g(n))$ 이고,  $f(n)=\Omega (g(n))$ 이라면

$f(n)$은 $g(n)$ 과 같은 속도로 증가한다.

즉, $f(n)=\Theta (g(n))$ 이다.

 

컴퓨터 과학에서 시간 복잡도

알고리즘 문제를 풀다 보면 자주 나오는 시간 복잡도가 있다.

그 종류를 함께 살펴보자.

 

$O(1)$ - 상수 시간

 

입력 크기와 상관 없이 항상 똑같은 시간이 걸리는 경우를 말한다.

배열에서 특정 인덱스 값을 조회하는 경우, $O(1)$이 소요된다.

 

$O(logn)$ - 로그 시간

이진탐색 처럼 입력값을 반으로 나누고, 또 반으로 나누고 하는 알고리즘이 있을 것이다.

대개 계속해서 반으로 나누면 $logn$ 만큼이 걸린다.

 

$O(n)$ - 선형 시간

 

입력 크기에 비례하여 연산 횟수가 증가하는 것을 말한다.

for 반복문을 통해 배열의 모든 요소를 순차적으로 순회하는 경우를 말한다.

$O(n)$ 만큼 걸린다.

 

보통 반복문 하나를 사용하면 $O(n)$ 이다.

 

$O(n^2)$ - 제곱 시간

 

입력 크기의 제곱만큼 연산이 늘어나는 경우이다.

반복문을 두번 쓸 때 $O(n^2)$ 만큼 소요된다.

대표적인 예시로 버블정렬, 선택정렬, 삽입정렬이 있다.

 

$O(n\ast logn)$ - 선형 로그 시간

 

입력 크기에 로그 시간 만큼 연산 횟수가 증가하는 경우를 말한다.

버블정렬, 선택정렬보다 더 효율이 좋은 정렬 알고리즘이 있다.

힙 정렬, 병합 정렬의 경우 $O(n\ast logn)$ 만큼 걸린다.

퀵소트의 경우에는 최선, 평균적인 경우에 $O(n\ast logn)$ 만큼 소요된다.

 

 

$O(2^n)$ - 지수 시간

 

입력 크기가 증가할 수 록 연산 횟수도 지수 형태로 증가하는 알고리즘이 있다.

보통 재귀(Recursive)로 문제를 풀면 이런 시간복잡도가 나온다.

 

$O(n!)$ - 팩토리얼 시간

 

순열을 만드는 것 처럼 입력크기만큼 모든 경우의 수를 고려해야 하는 경우 

팩토리얼만큼 시간이 소요된다.