시간 복잡도, 공간 복잡도

알고리즘을 평가하는데 있어 수행시간과 메모리 사용량을 평가기준으로 두는데
수행시간에 해당하는 것이 시간 복잡도 Time Complexity,
메모리 사용량에 해당하는 것이 공간 복잡도 Space Complexity이다.

 

목차

• 시간 복잡도란?

• 빅오 표기법

• 공간 복잡도란?

• 공간 복잡도 예제

 

 

<시간 복잡도>

시간 복잡도란?

• big-O에 대한 시간 개념으로 알고리즘의 수행 시간이 얼마인지를 나타낸다.
• 수행되는 연산의 수를 가지고 계산하며 알고리즘에서 중요하지 않는 값들(상수항, 영향력 없는 항)은 최대한 무시한다. 즉 최고차항의 차수가 빅오가 된다.
• 알고리즘의 실행 순서를 따라가며 Elementary Operation이 일어나는 수를 측정한다.

Elementary Operation

프로그램 스텝에서 Elementary Operation이란 프로그램의 진행 정도를 나타내는 기본 단위이다.

1. 대입연산
2. 덧셈, 뺄셈, 곱셈, 나눗셈
3. 비교구문
4. 함수호출

 

빅오 표기법

• O(1) - 상수시간
  • 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.
• O(logN) - 로그시간
  
  • 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.
  • 이 유형은 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형이다.
  • ex) Binary Search
• O(N) - 직선적시간
  
  • 단계의 수와 입력값 n이 1:1의 관계를 가진다.
  • ex) linear search, for 문을 통한 탐색
• O(N^2) - 2차시간
  • 데이터양에 따라 걸리는 시간은 제곱에 비례한다. (효율이 좋지 않음, 사용하면 안된다)
  • 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱
  • 2중 for 문을 사용하는 버블소트, 삽입정렬(insertion sort), 이중 루프

 

시간복잡도 알고리즘 예

 

성능비교

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

 

<공간 복잡도>

공간 복잡도란?

• 공간에 대한 개념으로 알고리즘이 공간을 얼마나 필요로 하는지를 나타낸다.
• 크기가 N인 배열을 만든다고 가정하면 공간 복잡도가 O(N)이 되고 NxN인 배열을 만들면 O(N²)이 된다.
• 함수의 재귀적인 호출의 경우 스택 공간도 고려해야 한다.

공간 복잡도 예제

int mainSum(int N){
    int result = 0;

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

    return result;
}

int sum(int a, int b){
    return a + b;

mainSum()함수에서 sum()를 N번 호출하지만 스택에 쌓이는 최대 공간은 mainSum() + sum(), 2이다.

따라서 이 경우의 공간 복잡도는 O(1)이다.