공간복잡도란 ?
공간복잡도란 주어진 문제를 해결하는 데 사용되는 공간의 상관관계이다.
대부분의 문제들은 128MB, 256MB, 512MB 내의 공간복잡도를 조건으로 주어진다.
공간복잡도 계산 ?
정수 타입의 int 를 기준으로 문제에서 사용 가능한 공간을 대략적으로 측정해 보았다.
- 128MB : 공간 3300개
- 256MB : 공간 6600개
- 512MB : 공간 1.2억개
알아둔다면 배열을 사용하거나 다른 자료형을 사용할 때 시간복잡도와의 Trade-off 관계 계산에 유용하다.
시간복잡도란 ?
시간복잡도란 주어진 문제를 해결하는 데 걸리는 시간의 상관관계이다.
대부분의 문제들은 1초, 2초 내의 시간복잡도를 조건으로 주어진다.
시간복잡도 특징 ?
시간복잡도의 시간은 컴퓨터의 연산 횟수를 뜻하며, 아래에 특징을 정리해 보았다.
- 주어지는 1초는 Java 기준으로 대략 1억 번의 연산 처리 수행 조건을 의미한다.
- 언제나 최악의 경우를 생각한다.
- 최고차 항만을 표기하는 빅오표기법을 적용한다.
시간복잡도의 특징은 문제를 접근하고, 해결하는데 필요한 것들이기 때문에 꼭 알아두자.
시간복잡도 종류와 비교 ?
| 종류 | 시간복잡도 | 예시 |
| 상수형 | O(1) | 배열의 특정 인덱스 값 접근 |
| 로그형 | O(logN) | 정렬된 정수 배열 이분 탐색 |
| 선형 | O(N) | 배열의 순회 정렬되지 않은 배열내 특정 값 찾기 |
| 선형로그형 | O(NlogN) | 일반적인 정렬 (힙 정렬, 퀵 정렬, 병합 정렬) |
| 2차형 | O(N²) | 버블 정렬, 삽입 정렬, 선택 정렬 |
| 3차형 | O(N³) | 플로이드-워셜 |
| 지수형 | O(2ⁿ) | 조합 |
| 팩토리얼형 | O(N!) | 중복 순열 |
상수형 > 로그형 > 선형 > 선형로그형 > 2차형 > 3차형 > 지수형 > 팩토리얼형 순으로 빠르다.
시간복잡도 계산 ?
빅오 표기법에 따라 1초 기준으로 문제 해결이 가능한 범위를 대략적으로 측정해 보았다.
| 종류 | 시간복잡도 | 범위 |
| 상수형 | O(1) | - |
| 로그형 | O(logN) | - |
| 선형 | O(N) | 1억 |
| 선형로그형 | O(NlogN) | 420만 |
| 2차형 | O(N²) | 1만 |
| 3차형 | O(N³) | 450 |
| 지수형 | O(2ⁿ) | 26 |
| 팩토리얼형 | O(N!) | 11 |
주어진 문제에 대한 알고리즘을 선택하는데 꼭 필요한 내용이므로, 꼭 알아두자.
Trade-off 관계 ?
시간복잡도와 공간복잡도를 조절해서 사용하면 주어진 문제를 해결하는데 큰 도움이 된다.
이해를 돕기 위해 피보나치 수열의 문제를 예시로 풀어보자.
재귀로 푼다면 중복된 연산에 의해 O(2ⁿ) 시간복잡도 소요
공간을 활용하여 중복을 없앤다면 O(N) 시간복잡도 소요
요약
- 자바 기준 1초에 1억의 연산을 수행한다.
- 최악의 경우로 시간복잡도를 계산한다.
- 빅오 표기법을 적용한다.
- 상수형 > 로그형 > 선형 > 선형로그형 > 2차형 > 3차형 > 지수형 > 팩토리얼형 순으로 빠르다.
'Computer Science > Algorithm' 카테고리의 다른 글
| [Algorithm] 완전탐색 - 부분집합 (0) | 2023.08.08 |
|---|---|
| [Algorithm] 완전탐색 - 조합 (0) | 2023.08.08 |
| [Algorithm] 완전탐색 - 순열 (0) | 2023.08.08 |
| [Algorithm] 시간복잡도 문제 (0) | 2023.08.08 |
| [Algorithm] 알고리즘 기초 (0) | 2023.08.07 |
