빅오

빅오(O, big-O)란 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법이다.

점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기법

점근적 실행 시간: 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 $lim$ 함수의 실행 시간의 추이를 의미

컴퓨터의 빠른 처리 능력을 감안하면 입력의 크기가 작으면 금방 끝나버린다. 그러므로 충분히 큰 입력을 주어 알고리즘의 효율성에 따른 수행 시간을 알아보아야 한다.

입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구사항(공간 복잡도)이 어떻게 증가하는지 분류하는데 사용

알고리즘의 효율성 분석에서 유용하게 활용

점근적 실행 시간의 예시로 디스크에 있는 파일을 친구에게 보낼 때

파일 크기가 작다면, 즉 $n$이 작다면 $O(n)$의 시간이 걸리는 온라인 전송이 빠르다.

하지만 파일이 아주 크다면, 항상 일정한 시간이 소요되는($O(1)$의 시간이 걸리는) 비행기를 통해 물리적으로 배달하는 게 더 빠를 수 있다. (비용을 고려하지 않는다면)

점근적 실행 시간은 시간 복잡도라고 말할 수 있다.

시간 복잡도(Time Complexity)의 사전적 정의는

어떤 알고리즘을 수행하는 데 걸리는 시간을 설명한은 계산 복잡도(Computational Complexity)이다.

빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며, 상수항은 무시한다.

ex) 입력값 $n$에 대해 $4n^2+3n+4$번 만큼 계산하는 함수가 있다면 이 함수의 시간 복잡도는 최고차항인 $4n^2$만을 고려한다.

이 중에서도 계수는 무시하며 $n^2$만을 고려한다.

즉, 여기서의 시간 복잡도는 $O(n^2)$이 된다.

빅오 표기법의 종류