시간 복잡도 왜 필요한가?
- 정의 : 작동하는 알고리즘의 수행 시간을 정량화하는 것
- 가정 : 1초에 1억번 연산을 한다고 가정
- 문제 : 제한시간 10초의 문제가 있을 때 연산량을 10억 번 이하로 줄여야 하며
설계시에 시간 복잡도가 높으면 미리 낮추어야 함
- T(N)은 최악의 경우에만 연산횟수를 나타냄
예를 들어 N번 연산이 2번 필요한데
하나는 N번이 필수고, 다른 하나는 조건에 의해 최소 0~최대 N번의 연산이 필요할 때
Worst 케이스로 2N으로 표기
시간 복잡도 표기법
- 빅오 O(N) 표기법 : worst case 연산 횟수 표기
- 빅오메가 Ω(N) 표기법 : best case 연산 횟수 표기
- 빅세타 θ(N) 표기법 : 평균 case 연산 횟수 표기
일반적으로 빅오 표기법 사용
T(N)이 3N² 라고할때 빅오 표기법은 계수를 빼고 최고차 항의 차수만 남겨서
O(N²)로 표기함
시간복잡도 종류
상수형 O(1) : 길이가 N인 배열에서 M번째 배열 값 출력 시
선형 O(N) : 정렬되지 않은 길이가 N인 배열에서 가장 작은 수를 탐색
2 차형 O(N²) : 버블 정렬, 삽입 정렬, 퀵 정렬의 worst case
*삽입정렬 : N개의 숫자에서 가장 작은 수를 찾아서 가장 앞자리로 보내주고
다시 남은 N-1개의 숫자에서 위 알고리즘을 반복함
T(N) = N(N+1)/2 = 1/2N²+1/2N -> O(N²)
3차형 O(N³) : 플로이드-워셜 알고리즘
로그형 log₂N : N개의 정렬된 수열에서 이분 탐색을 통해 특정 숫자 입력 (2진 트리에서 원소의 개수는 log₂N개)
우선순위 큐, 힙에서의 원소 삽입/삭제 연산
팩토리얼형 O(N!) : 1~N까지 숫자를 나열하는 모든 방법 출력 (순열형)
지수형 O(2ⁿ) : 번호가 매겨진 N개의 동전 던질 때 나올 수 있는 경우 출력
선형 로그형 ON log₂N : 힙 정렬, 병합 정렬, 퀵 정렬의 Average case
공간복잡도 Space Complexity
- 정의 : 알고리즘 문제를 해결하기 위해 사용하는 메모리의 크기
java에서
char : 2bytes short : 2bytes int : 4bytes long : 8bytes float : 4bytes double : 8bytes
이기 때문에 256MB제한일 경우 6700만개 정도의 int 배열을 사용할 수 있음