1. Big-O (빅 오) 표기법 이란?
어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도 표기하는 대표적인 방법이 빅오 표기법.
알고리즘의 복잡도를 판단하는 척도로는 시간 복잡도와 공간 복잡도 두 가지가 있는데, 빅 오 표기법은 시간 복잡도를 다룬다.
알고리즘은 연산이 많아질수록 그 속도가 오래 걸린다.
따라서 시간 복잡도는 알고리즘 내 연산의 횟수와 관계가 있다.
2. 빅 오 표기법을 사용하는 이유
효율성을 상한선 기준으로 표기하기 때문
알고리즘 내에서 빅오 분석법을 사용할 때에는 worst-case를 가정한다.
즉, 가장 오래 걸릴 경우의 시간 복잡도를 표기함
알고리즘 효율성은 값이 클수록 즉, 그래프가 위로 향할수록 비효율적임을 의미한다.
3. 빅 오 표기법의 특징
- 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측 하는게 목표
상수항 무시 : 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다.
실제 알고리즘의 러닝타임을 재는 것이 목적이 아니기 때문
영향력 없는 항 무시 : 빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다.
4. 성능 비교
그래프가 위를 향할수록 성능이 떨어진다.
즉 시간복잡도 = n값의 증가에 따라 처리시간이 증가하는 정도.
( 상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수 )
왼쪽에서 오른쪽으로 갈수록 성능이 떨어진다
5. 예시
-
O(1) : 스택/큐 에서 Push, Pop
- 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
-
O(log n) : 이진트리, 이진검색
- 검색 할 때마다 반씩 필요가 없어지기 때문에 O(n)보다 시간이 덜 걸림
-
O(n) : for 문
- 입력 데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘
-
O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
-
O(n^2): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
- 데이터가 커지면 커질수록 시간도 훨씬 더 걸림
-
O(2^n) : 피보나치 수열
- 데이터가 커질수록 시간이 현저히 늘어남
참고자료 (Reference)
출처: https://noahlogs.tistory.com/27 [인생의 로그캣]
