본 게시물은 2021.01.15. 에 작성되었으며, 블로그를 이전하며 현재 날짜로 등록되었습니다.
"'파이썬 알고리즘 인터뷰 4장'을 참고해 빅오 표기법을 정리했습니다."
01. 빅오 표기법(big-O notation)란?
- 점근적 실행 시간 : 입력값 n이 무한대로 향할 때, 함수의 실행 시간 추이
- 점근적 실행 시간(asymptotic running time)을 달리 말하면 시간 복잡도
- 빅 오 표기법 = 시간 복잡도를 표기하는 대표적인 방법
02. rule of big-O notation
- 최고차항만을 표기하며, 상수항은 무시한다.
$4n^2+3n+4$ 라면 이 함수의 시간 복잡도는 최고차항인 $4n^2$ 이다.
03. big O의 종류
$$O(1)$$
- 입력값에 관계 없이 실행 시간이 상수로 일정하다.
ex) 해시테이블의 조회 및 삽입
$$O(log n)$$
- 매우 큰 입력값에도 크게 영향을 받지 않는 편
- 웬만한 n의 크기에 대해서도 매우 견고함
ex) 이진검색
$$O(n)$$
- 입력값에 시간복잡도가 비례한다.
ex) 선형시간 알고리즘(linear-time algorithm), 정렬되지 않은 리스트에서 최댓값 또는 최솟값 경우
$$O(n log n)$$
- 적어도 모든 수에 대해 한 번 이상은 비교해야하는 비교 기반 정렬 알고리즘도 O(n log n)보다 빠를 수 없음
- 입력값이 최선인 경우에는 비교를 건너뛰어 O(n)이 될 수 있음 ⇒ 팀소트(timsort)
- 병합정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘
$$O(n^2)$$
- 버블정렬같은 비효율적인 정렬 알고리즘이 이에 해당함
$$O(2^n)$$
- O(n^2)보다 훨씬 더 크다
ex) 피보나치 수를 재귀로 계산하는 알고리즘
$$O(n!)$$
- 가장 느린 알고리즘, 입력값이 조금만 커져도 웬만한 다항시간 내에는 계산이 어려움
ex) TPS(각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제)문제를 브루트 포스로 풀이할 때
04. 시간 복잡도와 공간 복잡도
- big O는 공간 복잡도를 표현하는 데에도 쓰인다.
- 알고리즘은 "시간과 공간이 트레이드오프(trade-off) 관계" 이다.
: 실행시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하면 실행 시간이 느리다.
05. 상한과 하한, 최선과 최악 그리고 평균
- 복잡한 함수 $f(n)$ 이 있다고 가정
- 이 함수가 가장 빨리 실행될 때 : 하한, 가장 늦게 실행될 때 : 상한
- 빅오표기법은 상한(가장 늦게 실행될 때), 빅 오메가 는 하한, 평균은 빅세타라고 지칭한다.
- 빅오 표기법은 n이 매우 클 때의 전체적인 큰 그림에 집중한다.
빅오 표기법은 주어진 (최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다.
반응형