코딩 인터뷰 완전분석 | 6. Big-O 알아보기

VI. Big-O

시간 복잡도

점근적 실행 시간 (asymptotic runtime), big-O

얼마나 시간이 소요되는지를 나타냄

 

O(big-O)

시간의 최대 상한

ex. x <100 인 경우, x <10000도 옳은 표현. 시간 복잡도를 O(N),  O(N^2) 으로도 작성할 수 있음

Ω(big-Omega)

등가 개념이나 하한 선

ϴ(big theta)

O와 Ω 모두, 딱 맞는 수행시간

 

최선의 경우 / 최악의 경우 / 평균의 경우

보통 최악과 평균이 같을 수도 있는데 알고리즘에서는 최악과 평균을 동시에 고려함

 

공간 복잡도

메모라(공간)을 사용하는 정도

 

표현 방식

상수항은 무시 ex. O(2N) => O(N)

지배적이지 않은 항(최고차항이 아닌 항)은 무시 ex. O(N+log N) => O(N)

 

수행 시간 계산

A 작업 후에 B 작업 수행 => A + B 수행시간

A 작업 할 때마다 B 작업도 수행 => A * B 수행시간

 

원소의 개수가 절반씩 줄어든면 수행 시간 O(log N)

로그의 밑은 상수 처리, 지수의 밑은 무시 X

재귀 함수 수행 시간 O(분기^깊이)

*분기: 재귀 함수가 재호출되는 횟수, 깊이: 호출된 함수 갯수