복잡도는 크게 공간 복잡도와 시간 복잡도로 나뉜다.
복잡도를 분석하는 것은 한 문제에 대해서 해결방법으로 나올수 있는 알고리즘이 여러개가 있기 때문이다.
그 다수의 알고리즘의 성능을 비교해야 할 필요가 있으므로 공간 / 시간 복잡도를 분석하여 표기한다.
이때 표기 방법에는 주로 점근적 표기법 (Asymptotic Notation)이 쓰인다.
시간 복잡도(Time Complexity)
-시간복잡도: 프로그램의 수행시간을 분석하는 것, 반복문에 크게 영향을 받음
-계산 방법
1) 연산 횟수의 함수가 주어진 경우
최고차항의 계수와 그보다 낮은 차수의 항을 제외시키면 된다.
예를 들어 7n^5+5n^3+3n^2+3 라는 식이 주어졌을때 최고차항인 7n^5 의 계수인 7과 나머지 5n^3+3n^2+3 를 제외 시켜 O(n^5)라고 표기해주면 된다.
2) 코드가 주어진 경우
- 보통 1억을 1초로 잡고 계산
- 연산의 횟수를 세고 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)를 구한다.
- 이때 모든 연산의 횟수를 세는 것이 아닌 알고리즘의 핵심이 되는 연산의 횟수만 계산한다.
- 핵심이 되는 연산이란 다른 연산에 의해 연산 횟수가 바뀌는 종속적인 연산이 아닌 연산을 찾으면 된다.
- 그 연산에서 최악의 경우를 찾아 빅 오 표기법(Big-O notation)으로 표기한다.
공간 복잡도(Space Complexity)
-공간복잡도: 프로그램의 메모리 사용량을 분석하는 것
-계산 방법
* 보통 기타 지역 변수나 헤더 파일, 함수 등을 생각해서 5-10MB는 제외하고 생각한다.
크기가 n인 배열에서 n x n의 이차원 배열을 생성한다면 이 알고리즘의 공간 복잡도는 n^2이 된다.
참고 사이트
'CS > Algorithm 이론' 카테고리의 다른 글
| [Algorithm] 덱 (Deque) (0) | 2019.11.03 |
|---|---|
| [Algorithm] 큐 (Queue) (0) | 2019.10.30 |
| [Algorithm] 스택 (Stack) (0) | 2019.10.30 |
| [Algorithm] 연결리스트(Linked List) (0) | 2019.10.17 |
| [Algorithm] 배열 (0) | 2019.10.14 |