시간복잡도에 관한 구체적이고 쉬운 이야기

Time Complexity
시간 복잡도

 

시간복잡도란?

시간복잡도는 문제 해결을 위한 알고리즘의 로직을 코드로 구현할 때 '입력값의 변화에 따라 연산이 실행될 경우, 연산 횟수에 비례해 시간이 얼마만큼 소요되는가'를 나타내는 것이며 Big-O 표기법을 사용해 나타낸다

 

2가지 코드가 있다.

int n, sum = 0; scanf("%d", &n); for(int i=1;i<=n;i++){      sum += i; } printf("%d", sum);

int n, sum=0; scanf("%d", &n); sum = n*(n+1)/2; printf("%d", sum);

왼쪽 코드의 경우 반복물을 이용해 1부터 n까지의 합을 계산했고

오른쪽 코드의 경우 1부터 n까지를 합공식인 n(n+1)/2을 이용해서 계산했다.

 

두개의 코드는 결과값은 같지만 연산 속도가 다르다

 

왼쪽 코드의 경우 n이 100일 경우 100번 연산, 10000일경우 10000번 연산 등 n만큼의 연산이 일어나게 된다

오른쪽 코드의 경우 n의 크기와 상관없이 곰셈, 덧셈, 나눗셈 각 1번씩만을 하여 n의 크기와 상관없이 연산이 일어난다.

 

위의 예시와 같이 모든 알고리즘들은 입력되는 데이터 값의 변화와 연산이 실행된 후 연산 횟수에 비례해 시간이 소요되는 것을 최대한 효율적으로 짜고자 Big-O 표기법을 이용해 최대한 시간복잡도를 줄이는 것이다.

 

입력된 데이터의 갯수가 n개일 경우 3n+2번 계산하는 알고리즘과 3n번 계산하는 알고리즘이 존재한다고 가정하자

n이 1, 10, 100등일 경우 두 알고리즘은 차이가 존재할 수 있으나 n이 커지면 커질수록 둘의 차이는 무의미 해진다

따라서 O(2n+7) = O(2n)와 같이 보는 것이다.

 

Big-O 표기법에서는 계산 횟수에 붙은 상수는 중요하지 않다고 판단해 제외하여 표기한다

 

위의 예시코드에서 왼쪽 코드는 O(n)의 시간복잡도를, 그리고 오른쪽 코드는 O(1)의 시간복잡도를 가지고 있다

한눈에 보아도 O(n)보단 O(1)이 훨씬 빨라 보이지 않는가?

 

이와 같이 시간복잡도는 보통

시간복잡도	설명
O(1)	상수형태, n의 크기와 상관없이 일정한 양의 연산
O(log n)	로그형태
O(n)	선형
O(nlogn)	선형 로그 형태
O(n^2), O(n^3),,,	다차 형태
O(2^n)	지수형태
O(n!)	팩토리얼 형태

이와 같은 형태가 많이 사용된다

 

또한 알고리즘의 코드중 최악의 경우를 고려하여 그 알고리즘의 시간복잡도를 나타낸다

가령 최선의 경우 1초, 평균적으로 5분, 최악의 경우 1시간이 걸리는 알고리즘을 구현했을 때

최선의 경우 혹은 평균을 고려한 표기를 할경우엔 실제 걸린 시간이 1시간이 넘게 걸린다면 어디서 문제가 발생한지에 대하여 의문이 생길 것이다.

극단적인 예지만 항상 최악의 경우도 고려하여 대비하는 것이 바람직한 방법이므로 

Big-O표기법은 가장 많이 걸리는 시간복잡도를 선택하여 표기하는 것이다.

 

위의 표기법에 따르면 O(2n) 역시 O(n)으로 표기하는 것이 바람직하다.