big-O

big-O 시간은 알고리즘의 효율성을 나타내는 지표이다.

비유하기

디스크에 있는 파일을 다른 지역에 살고있는 친구에게 가능하면 빨리 보내려고 한다.

온라인을 통한 전송 vs 직접 전달
만약 파일 크기가 작다면 온라인을 통한 전송이 빠를 것이지만, 파일 크기가 아주 크다면 물리적으로 전달하는 방식이 더 빠를 수 있다.

시간 복잡도

이런 것을 점근적 실행 시간, 또는 big-O 시간에 대한 개념이다.위의 예를 다음과 같이 설명할 수 있다.

온라인 전송: O(s), 여기서 s는 파일의 크기가 된다. 즉, 파일의 크기가 증가함에 따라 전송 시간 또한 선형적으로 증가한다.

직접 전달: 파일 크기에 관계없이 O(1), 파일의 크기가 증가한다고 해서 파일을 전달하는 데 걸리는 시간이 늘어나지 않는다. 즉, 상수 시간 만큼 소요된다.

상수가 얼마나 큰지 아니면 선형식이 얼마나 천천히 증가하는지(기울기)에 관계없이 숫자가 커지다보면 선형식은 언젠가 상수를 뛰어넘게 된다.
실행 시간에 다양한 변수가 포함될 수도 있다. 예를 들어, 너비가 w미터이고 높이가 h미터인 울타리를 색칠하는 데 소요되는 시간은 O(wh)로 표기할 수 있다. 만약 페인트를 p번 덧칠해야 한다면, O(whp)의 시간이 소요된다고 말할 수 있다.

big-O, big-𝚯, big-Ω

O(big-O): 학계에서 big-O는 시간의 상한을 나타낸다. 배열의 보든 값을 출력하는 알고리즘은 O(N)으로 표현할 수 있지만, 이외의 N보다 큰 big-O 시간으로 표현할 수도 있다. 예를 들어, O(N^2), O(N^3), O(2^N)도 옳은 표현이다. 하지만 업계에서 말하는 big-O는 big-𝚯의 의미와 가깝다.

Ω(big-Ω): 학계에서 Ω는 등가 개념 혹은 하한을 나타낸다. 배열의 모든 값을 출력하는 알고리즘은 Ω(N)뿐만 아니라 Ω(logN) 혹은 Ω(1)로도 표현할 수 있다. 결국, 해당 알고리즘은 Ω 수행시간보다 빠를 수 없게 된다.

𝚯(big-𝚯): 학계에서 𝚯는 O와 Ω 둘 다를 의미한다. 즉, 어떤 알고지름의 수행 시간이 O(N)이면서 Ω(N)이라면, 이 알고리즘의 수행 시간을 𝚯(N)으로 표현할 수 있다.

Photo by Mark König on Unsplash
코딩 인터뷰 완전 분석