빅오 표기법

1. 빅오란? (O, big-O)

빅오(O, big-O)란 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기방법이다. 란다우 표기법이라고도 하며 점근 표기법의 일종으로 빅오는 점근적 실행시간을 표현하기 위해 사용한다. 점근적 실행 시간이란 입력값 n이 커질 때, 즉 입력 값이 무한대를 향할 때 실행 시간의 추이를 의미한다. 빅오(O)는 상한을 의미한다. 이외에도 하한을 표현하는 빅 오메가, 평균을 의미하는 빅세타 등이 있지만 상한으로 표현하는 표현법을 널리 사용한다.

컴퓨터 사이언스에서 빅오는 알고리즘의 성능을 표현하는 데 주로 사용하며 시간과 공간 복잡도를 표현할 수 있다. 알고리즘의 실제 성능을 표현하는 표기법이 아님을 기억해야한다.

2. 빅오의 예시

- O(1)

빅오에서 상수는 입력한 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 의미한다.

- O(n)

선형시간복잡도를 나타낸다. 문제를 해결하기 위해 입력된 데이터인 n의 크기만큼 처리 시간이 걸리는 알고리즘을 나타낼 때이다. n 과 처리 시간이 일정하게 비례하여 증가하는 특성이 있다.

- O(n^m)

다항시간복잡도는 n 개의 각 루프 안에 또 m 개의 루프를 가질 때 O(n^m) 이 된다. 문제를 해결하기 위한 처리 시간이 n의 m만큼 제곱한 시간이다. 데이터의 개수가 커질수록 시간복잡도는 기하급수적으로 증가하게 되므로 중첩 for문을 작성할 땐 조심스럽게 작성해야한다.

-  O(log n)

문제를 해결할 때 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다. 문제를 일정한 크기의 작은 문제로 분리할 때 도출되게 된다. 대표적으로 이진 검색(Binary Search)를 예로 들 수 있다.

References

1. https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95

2. 유튜브 엔지니어 대한민국

[자료구조 알고리즘] 빅오(Big-O)표기법 완전정복 - https://www.youtube.com/watch?v=6Iq5iMCVsXA 

3. https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/

4. https://velog.io/@bathingape/Time-Complexity%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84