빅 오(Big-O)와 시간복잡도

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)

알고리즘의 성능을 평가하는 요소는 크게 두 가지가 있다. 첫 번째는 어떤 알고리즘이 어떠한 상황에서 더 빠르냐?이고 두 번째는 어떤 알고리즘이 어떠한 상황에서 메모리를 더 많이 쓰냐?이다. 전자는 속도에 관한 것이고 후자는 메모리 사용량에 관한 것이다. 이에 해당하는 알고리즘의 수행결과를 분석한 결과를 가리켜 각각 시간 복잡도(time complexity)와 공간 복잡도(space complexity)라 한다.

과거 메모리 용량이 매우 부족하던 시절이나 특수한 상황에서 알고리즘을 적용할 때를 제외하고는 보통 공간 복잡도보다는 시간 복잡도에 초점을 둔다. 왜냐하면 오늘날의 메모리는 알고리즘에 영향을 받을만큼 작지 않기 때문이다.

시간 복잡도 분석

순차 탐색

이진 탐색

빅 오(Big-O), 빅 세타(Big-theta), 빅 오메가(Big-omega)