[알고리즘] 복잡도 (시간복잡도, 공간복잡도) 알아보기

 

알고리즘 성능 평가시 `복잡도(Complexity)` 를 이용해 성능을 평가한다. 

동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라 말한다.

• 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
• 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

 

알고리즘은 Correctness(문제해결), Efficiency(효과적으로 해결)이 기준이다.

정확성, 작업량, 기억 장소 사용량, 최적성, 복잡도(빅O 표기법=점근표기법)를 이용해 Efficiency를 판단한다

 

1. 시간 복잡도 (TC)

"얼마나 빠르게 실행되느냐"

 

시간 복잡도는 말그대로 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 
반복문과 같이 코드 성능에 영향을 많이 주는 부분을 파악해 실행시간을 예측한다.

Big-Ω(오메가) : 최선의 경우를 말한다. 한 번에 찾을 때, 즉 가장 빠른 시간이 걸리는 것 
Big-O : 최악의 경우를 말한다. 배열의 길이만큼 걸리거나 작업완료까지 가장 느린 시간을 말한다.
Big-Θ(세타) : 평균의 경우를 말한다. 여러가지 다른 경우의 수를 입력하여, 총실행시간을 계산하고 시행횟수로 나눈다.

와 같은 표기법이 있지만 일반적으로 Big-O로 나타낸다.

 

빅-오 표기법 (Big-O)

1. 최악의 경우를 계산하고 
2. 상수는 제거하고 더 큰 값만 남긴다, 즉 가장 영향이 큰 값만 남겨서 표현한다
3. 그리고 변수가 다를경우 별도로 분리해서 적는다

는 원칙을 가지고 있다.

이런 점근표기법은 정확한 실행시간을 계산하지않고 대략적으로 불필요한 연산을 제거한 값을 표현한다.
코드의 실행시간은 모든 플랫폼, 컴퓨터등 동일한 환경이 갖춰지지 않는다면 항상 다른 결과가 나올 것이기 때문에 이를 기준으로 삼기에는 적합하지 않다.

 

대표적인 자료구조에 대한 시간복잡도는 아래 표와 같다.

추가로, 피보나치수열 같은 경우 O(2^n)을 나타낸다. 

이중에 `O(log n)`은 binary search를 할 때 나타나는 시간복잡도로,

예를 들어 1부터 10까지 목록중에 7을 찾을경우
5보다 큰지 작은지를 먼저 물어봐서 값의 범위를 절반씩 줄여나가면서 찾는 것이 효율적이다.

이와 같이 범위의 절반씩을 줄여나가는 연산을 할 때 나타나는 시간복잡도이다.

`O(sqrt(n)` 은 제곱근을 나타내는 시간복잡도이기 때문에, 
아래 사진과 같은 경우 나타난다.

 

 

리스트와 관련된 시간복잡도

사전과 관련된 시간복잡도

 

2. 공간 복잡도 (SC, Space Complexity)

"얼마나 많은 자원이 필요한가?"

공간 복잡도란 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석한다.
(컴퓨터 성능의 발달로 메모리 공간이 증가하다보니, 시간복잡도에 비해 중요도는 떨어진다.)

• 총 필요 저장공간
  • 고정 공간(알고리즘과 무관) : 코드 저장공간, 단순 변수 및 상수
  • 가변 공간(알고리즘 실행과 관련) : 실행 중 동적으로 필요한 공간으로, TC를 무시한다면 이를 이용하는 것이 효율적이다.

 

가변공간을 사용하는 알고리즘이 공간복잡도의 효율면에서 좋지만,
시간복잡도와 공간복잡도는 반비례적인 경향을 보이고 알고리즘은 시간복잡도가 중심임을 기억해두어야한다.

공간 복잡도에 영향을 미치는 요소는 변수, 자료구조(Data Structure), 함수 호출(Function Call), 할당(Allocation) 네 가지입니다. 
 
O(1) : 입력 크기에 관계 없이 고정된 메모리 공간을 사용하는 알고리즘 (상수 공간 알고리즘)
- 예시 : 변수 하나를 사용하는 경우
O(n) : 입력 크기에 비례하여 메모리 공간을 사용하는 알고리즘 (선형 공간 알고리즘)
- 예시 : 배열, 객체 등이 사용되는 경우
O(n^2) : 입력 크기의 제곱에 비례하여 메모리 공간을 사용하는 알고리즘 (이차 공간 알고리즘)
- 예시 : 2차원 배열 등이 사용되는 경우
O(2^n) : 입력 크기가 커질수록 기하급수적으로 메모리 공간을 사용하는 알고리즘 (지수 공간 알고리즘)
- 예시 : 재귀 함수 등이 사용되는 경우

 

참고
아래 글을 보고 정리한 내용입니다.
https://velog.io/@cha-suyeon/Algorithm-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84
https://velog.io/@leemember/%EC%BD%94%ED%85%8C-%EB%8C%80%EB%B9%84-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
 https://overcome-the-limits.tistory.com/entry/자료구조-시간복잡도-with-JavaScript