[알고리즘] 시간복잡도와 공간복잡도 (1)

시간복잡도와 공간복잡도는 알고리즘의 성능을 판단하는 척도 중 하나입니다.

그 전에 먼저 알고리즘이 뭔지에 대해 알아보겠습니다.

알고리즘은 어떤 결과를 얻기위한 과정들을 말합니다.

예를 들면 집에서 PC방을 가려고합니다.

PC방을 가는 방법은 도보, 자전거, 자동차 등 여러가지가 있습니다.

이러한 방법들을 알고리즘이라고 생각하시면됩니다.

그러면 이 방법들 중 하나를 선택해서 PC방을 가야합니다.

선택하는 기준은 빨리 갈 수 있는 것이 될 수 있고, 자원(돈)이 들지 않는 것이 될 수 있습니다.

빨리 간다는 것은 시간을 절약하는 것이 되고, 이것을 시간복잡도라고 생각하시면됩니다.

자원이 들지 않는 다는 것은 공간복잡도 개념이라고 이해하시면 됩니다.

좋은 알고리즘은 시간이 적게 들고, 자원도 적게 드는 것입니다.

알고리즘을 평가하는데는 시간에 해당하는 시간복잡도와 자원 사용량에 해당하는 공간복잡도가 있습니다.

아래에서는 시간 복잡도에 대해 알아보겠습니다.

 

1. 시간 복잡도

시간 복잡도는 컴퓨터 프로그램의 입력 값과 연산 수행 시간의 상관관계를 수치적으로 나타낸 것입니다.

이런 시간 복잡도는 수치로 나타낼 수 있습니다.

수치로 나타내야지 비교를 할 수 있기 때문입니다.

수치가 낮을수록 좋은 알고리즘입니다.

시간 복잡도는 많이 들어보신 빅-오 표기법을 사용하여 나타냅니다.

빅-오 표기법은 계수와 낮은 차수의 항을 제외시켜 버리기 때문에 간략히 표현할 수 있습니다.

결론적으로는 최고차항의 차수가 빅오가 됩니다.

예를 들어 알고리즘의 시간이 10n^2 + 5n의 식을 가진다면 이 알고리즘의 시간 복잡도는 아래와 같이 표현합니다.

O(n^2)

시간 복잡도에서 중요하게 보는 것은 입력값인 n입니다.

빅오 표기법의 형태에 대해 아래에서 간단히 설명을 드리겠습니다.

1) O(1) 상수형태

 

입력값 n이 주어졌을 경우, 알고리즘이 문제를 해결하는데 오직 한단계만 처리하는 경우입니다.

ex) 출력문, if문, 스택에서 push 또는 pop 등

printf("Hello World!\n");

 

2) O(logn) 로그 형태

 

입력값 n이 주어졌을 경우, d문제를 해결하는데 필요한 단계들이 연산에 의해 특정 요인들이 줄어드는 경우

 

ex ) 이진 트리 등

3) O(n) 선형

 

문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가지는 경우

10n + 30 -> O(n)

ex ) 루프문으로 처리를 하는 경우

for ( idx = 0 ; idx < 10 ; idx++ )
    printf("idx = %d\n", idx);

4) O(nlogn) 선형 로그

 

ex) 퀵 정렬, 병합정렬, 힙정렬 등

 

5) O(n^2,3,4 ...) 다차 형태

 

문제를 해결하기 위한 단계의 수가 입력값 n의 다차 제곱일 경우

10n^2 + 40 -> O(n^2)

ex) 이중 루프문으로 처리를 하는 경우, 삽입정렬, 버블정렬, 선택정렬 등

for ( idx1 = 0 ; idx1 < 10 ; idx1++ )
{
    for ( idx2 = 0 ; idx2 < idx1 ; idx2++ )
        printf("idx1 = %d, idx2 = %d\n", idx1, idx2);
}

시간 복잡도에 대한 성능별 그래프는 아래와 같습니다.

6) O(a^n) 지수 형태

 

문제를 풀기 위한 단계의 수가 주어진 상수값에 입력값 n 제곱인 경우

 

ex) 피보나치 수열 O(2^n) 등

 

7) O(n!) 팩토리얼 형태

 

 

위의 7가지는 일반적으로 위로 갈수록 알고리즘의 빠르고, 아래로 갈수록 시간이 증가합니다.

 

아래는 빅오표기법의 성능을 그래프로 나타난 것입니다.

 

그래프만 보더라도 각각에 대한 성능치를 알 수 있습니다.

오늘 포스팅은 여기까지 하겠습니다.