코딩테스트 기초 작업
- 시간 복잡도의 표기
알고리즘의 효율성은 알고리즘의 수행 시간(시간 복잡도) 또는 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기(공간 복잡도)로 나타낼 수 있다.
복잡도의 경우 3가지 방법으로 나뉘게 된다.
| 최악 경우 분석 | 평균 경우 분석 | 최선 경우 분석 |
|---|---|---|
| 어떤 입력이 주어지더라도 알고리즘의 수행 시간이 일정 이상은 넘어가지 않는다. 보통 시간복잡도를 이야기한다면 이 쪽 이야기 | 평균적인 시간 계산 | 최적의 상황이 때의 시간 복잡도 |
상각 분석
알고리즘의 시간 복잡도를 분석하는 기법
연산의 수행 횟수/시간이 독립적으로 결정되지 않고 가변적인 경우(앞서 수행한 연산에 따라 실행 시간이 달라지거나 할 때) 사용함.종류
합체 분석 : 해당 연산의 호출 전체에 대한 최악의 수행시간을 분석하고 이를 호출 횟수에 나누어 상각 시간을 계산
회계 방법 : 먼저 사용하는 연산 종류별로 상각 시간을 할당하고, 실제 연산을 수행할 때 생성되는 자료구조에 회계 장부를 만들어 예치와 인출을 통해 관리하는 방법
위치 에너지 방법 : 각 연산에 상각 시가을 할당하고 남는 상각 시간을 위치 에너지로 보관하거나 실제 수행 시간에 모자라는 시간을 위치 에너지에서 빼서 보충하는 방법
시간 복잡도의 점근적 표기
- 빅 O(big-o) 표기법
점근적 상한을 나타내는 표기법이자 시간 복잡도 표기법 중 가장 자주 사용되는 방법
▢ O(1) - 상수 시간
▢ O(logn) - 로그(대수) 시간
▢ O(n) - 선형 시간
▢ O(nlogn) - 로그 선형 시간
▢ O(n^2) - 이차 시간
▢ O(n^3) - 3차 시간
▢ O(2^n) - 지수 시간
- 빅 오메가 표기법
빅 o와 달리 하한선을 정한다. 즉 연산이 이 이하로 떨어지지 않는다는 것을 의미한다.
- 세타 표기법
위의 두 개(빅 오, 빅 오메가)가 동일할 경우에 사용함.
