[ 알고리즘 ] 시간 복잡도 구하는 법

시간 복잡도에 대해서 많이 들어보셨을텐데요. 이 시간 복잡도를 구하는 방법을 알아보겠습니다.

 

 

시간 복잡도란?

기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다.

- 위키피디아-

 

시간 복잡도의 종류에는 크게 3가지가 있습니다.

=>  O(Big-O), Ω(Omega), Θ(Theta)

보통은 Big-O 표기법을 사용하여 시간 복잡도를 나타내기 때문에 Big-O 표기법만 다뤄보겠습니다.

( 더 궁금하신 분들은 검색을,,)

 

코드를 예시로 하여 좀 더 알아보겠습니다.

int sum = 0;

for(int i =0; i<N; i++)
	sum +=i;
    
    
==================================

int sum = (N+1)*N/2;

 

첫번째 코드는 sum=0 한 번, int i =1이 한 번 i++이 N번, sum+=i가 N번 합쳐서 총 2N+2번의 연산이 수행되었습니다.

Big-O 표기법에서는 최대 차항만 계수없이 표기하면 되기 때문에 O(N)이 됩니다.

 

두번째 코드는 N+1이 한 번, *N이 한 번, /2가 한 번, 계산된 값을 sum에 대입할 때 한 번

이렇게 총 네번이므로 4가 됩니다. Big-O 표기법으로는 O(1)이 되겠죠.

 

다시 이중포문을 예시로 들어보겠습니다.

 

int sum = 0;
for(int i = 0; i<N; i++)
	for(int j = 0; j<i; j++)
    		sum += j;
          
=======================================

int sum = 0;
for(int i =N; i>0; i/=2)
	for(int j = 0; j<i; j++)
    		sum += j;
            

첫 번째 코드의 바깥쪽 반복문은 N번, 안쪽 반복문은 i의 값에 따라 반복합니다.

i는 0부터 N-1까지 변하고 안쪽 반복문은 해당하는 i만큼 반복하므로 0+1+2+..+(N-1) = N*(N-1)/2번(등차수열의 합 공식) 반복합니다.

 

따라서 O(N²)이 됩니다.

 

두 번째 코드는 바깥쪽 반복문이 lgN번 반복, 안쪽 반복문은 i의 값에 따라 반복 횟수가 다릅니다.

(lgN번 반복인 이유는 i/=2 이기 때문입니다)

i는 N부터 1까지 변하고, 안쪽 반목문은 해당하는 i만큼 반복하므로 N+N/2+N/4+...+1 = 2N번 반복하므로 O(N)이 됩니다.

 

즉 Big-O표기법을 간단하게 정리하면

1) 가장 높은 차수만 남긴다

O(n² + n) -> O(n²)

2) 계수 및 상수는 과감하게 버린다.

O(2n + 3) -> O(n)

 

이렇게 보면 쉬울 겁니다. (아마두,,)

 

 

 

 

참고: medium.com/humanscape-tech/%EC%BD%94%EB%93%9C%EC%9D%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0-b67dd8625966