빅오(Big-o) 표기법

빅오 표기법?

알고리즘 성능을 분석할 때 사용하는 표현 방식이다. 정확한 계산을 위한 표기법은 아니다.

눈대중용 표기법이라 생각하고 편하게 보자.

 

종류

 

- O(1) : 상수형

입력 데이터 크기와 상관 없이 알고리즘 실행 시간이 일정함.

ex) 배열 등에서 인덱스를 사용할 때

 

- O(log n) : 로그형

데이터 크기의 로그에 비례하여 증가함.

ex) 이진 탐색 (트리 구조 등)

 

- O(n) : 선형

입력 데이터의 크기와 비례하여 실행 시간이 증가함.

ex) 배열의 검색, 배열 모든 요소 순회 등

 

- O(n log n) : 선형로그형

 

- O(n^2) : 제곱형

데이터 크기의 제곱에 비례해 실행시간이 증가함.

ex) 2중첩 반복문을 사용하는 알고리즘

 

- O(n^n) : 지수형

데이터의 크기의 N제곱에 비례해 실행시간이 폭발적으로 증가함.

ex) 다중 중첩 for()문

 

- O(n!) : 팩토리얼형

데이터 크기가 클수록 연산 수가 소요 시간이 기하급수적으로 증가함.