ssung_항해일지/CS 지식 및 기술면접

시간 복잡도(Time Complexity) 와 공간 복잡도 (Space Complexity)

ssungcohol 2023. 4. 25. 18:42

알고리즘을 평가할 때 시간 복잡도와 공간 복잡도를 사용한다.

  • 시간 복잡도 = 알고리즘의 수행 시간 평가
  • 공간 복잡도 : 알고리즘 수행에 필요한 메모리 양을 평가

시간 복잡도와 공간 복잡도는 주로 점근적 표기법 중 빅오 표기법을 이용해 나타낸다.

이유는 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해 볼 수 있기 때문이다.


시간 복잡도 (Time Complexity)

수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가한다.

 

기본 연산

  • 데이터 입출력 - copy, move ...
  • 산술 연산 - add, multiply ...
  • 제어 연산 - if, while ...

시간 복잡도는 세 가지의 경우로 나타낼 수 있다

1. 최선의 경우 (Best Case)

  • 빅 오메가 표기법 사용
  • 최선의 시나리오 적용

2. 최악의 경우 (Worst Case)

  • 빅 오 표기법 사용
  • 최악의 시나리오

3. 평균적인 경우 (Average Case)

  • 빅 세타 표기법 사용
  • 평균 시간을 나타냄

평균적인 경우를 가장 많이 사용할 것 같지만, 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어려워지기 때문에 최악의 경우로 알고리즘의 성능을 파악한다.


시간 복잡도 계산

시간 복잡도는 일반적으로 빅오 표기법으로 나타낸다.

연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항과 최고차항의 계수를 제외시켜 나타낸다.

 

Ex)

int func (int n) {
	int sum = 0;	// 대입연산 1회
    int i = 0;	// 대입연산 1회
    
    for (i = 0; i < n; i++) {	// 반복문 n+1회
    	sum += i;	// 덧셈 연산 n회
    }
    
    for (i = 0; i < n; i++) {	// 반복문 n+1회
    	sum += i;	// 덧셈 연산 n회
    }
    return sum;	// 리턴 1회
}

위 알고리즘에 단계별 연산회수는 주석과 같고 총 연산 횟수는 4n + 5이다.

따라서 이 알고리즘의 시간 복잡도는

T(n) = 4n + 5 = O(n) 이다.


시간 복잡도 표기

 

O(1) - 상수 시간 (Constant time)

  • 입력 크기(n)에 상관없이 일정한 연산을 수행하면 시간복잡도는 O(1)
void func (int n) {
  printf("%d\n", n);
}

위 알고리즘은 n에 상관없이 한 번의 연산만 수행하기 때문에 시간 복잡도 T(n) = O(1) 이다.

 

O(logN) - 로그 시간 (Logarithmic time)

  • 입력 크기(N)가 커질 때 연산 횟수가 logN에 비례해서 증가하면 시간 복잡도는 O(logN)입니다.
for(i=1; i<=n; i*2) {
  ...
}

이 알고리즘은 i 값이 반복할 때마다 2배씩 증가한다. 이것을 k번 반복 했을 때는 2^k = N이 되고 반복문이 종료된다.

양 변에 log를 취한 후 계산하게 되면 k = log2N이 된다

k는 수행 횟수이기 때문에 시간 복잡도 T(n) = logN이 된다.

 

O(n) - 선형 시간(Linear time)

  • 입력 크기(n)가 커질 때 연산 횟수가 n에 비례해서 증가하면 시간 복잡도는 O(n)이다.
    • 연산 횟수가 선형적으로 증가하는 형태
for(i=0; i < n; i++) {
  ...
}

이 알고리즘은 n만큼 반복문을 수행한다. n의 값에 비례하여 연산수가 선형적으로 증가하기 때문에 시간 복잡도

T(n) = O(n)이다.

 

O(n^2) - 2차 시간(Quadratic time)

  • 입력 크기(n)가 커질 때 연산 횟수가 n^2이 비례해서 증가하면 시간 복잡도는 O(n^2)이다.
or(i=0; i < n; i++) {
  for(j=0, j < n; j++) {
    ...
  }
}

이 알고리즘은 for문이 중접되어 있기 때문에 n^2에 비례해서 연산수가 증가한다. 시간 복잡도 T(n) = O(n^2)이다.

 

O(2^n) - 지수 시간 (Exponential time)

입력 크기가 커질 때 연산수가 2^n에 비례해서 증가하면 시간 복잡도는 O(2^n)이다.

int func (int n) {
  if (n <= 1) 
    return n;
  return func(n-1) + fun(n-2);
}

이 알고리즘은 피보나치 수를 구하는 알고리즘으로, 한 번 함수를 호출할 때마다 두 번씩 재귀로 함수를 호출하기 때문에

2^n 에 비례하여 연산수가 증가한다.

시간 복잡도 T(n) = O(2^n)이다.


공간 복잡도 (Space Complexity)

  • 공간 복잡도는 보조공간(Auxiliary Space)과 입력 공간(input size)을 합친 포괄적인 개념
  • 보조 공간은 알고리즘이 실행되는 동안 사용하는 임시 공간
  • 따라서 입력 공간을 고려하지 않음

공간 복잡도 계산

  • 공간복잡도도 시간 복잡도와 유사하게 빅오 표기법을 사용
int sum(int arr[], int n)
{
  int x = 0;		
  for(int i = 0; i < n; i++) {
    x  = x + a[i];
  }
  return(x);
}

이 알고리즘은 4개의 변수를 사용

  • int arr[n] : 4n byte (입력 공간)
  • int n : 4 byte (입력 공간)
  • int x : 4 byte (보조 공간)
  • int i : 4 byte (보조 공간)

총 4n + 12에 메모리를 요구. 메모리가 입력 값에 따라 선형적으로 증가하기 때문에 공간 복잡도는 O(n)이다.

728x90

'ssung_항해일지 > CS 지식 및 기술면접' 카테고리의 다른 글

DI (Dependency Injection)  (0) 2023.05.09
REST API  (0) 2023.05.08
객체지향 프로그래밍(OOP)  (0) 2023.05.08
CORS란 무엇일까?  (0) 2023.04.25
배열과 링크드리스트  (0) 2023.04.25