Big-O 표기법

Big-O 표기법이란?

• 알고리즘의 시간 복잡도를 나타내는 표기법
• 최악의 성능을 측정합니다
  

Big-O 표기법의 특징

• 상수항 무시 : 단순히 증가하는 비율을 나타내는 개념이므로, 시간복잡도를 계산할때는 상수항을 무시한다.
  ex) 3n + 2n = 5n = O(n)
• 지배적이지 않은 항 무시 : 수식에서 가장 영향력이 있는 항을 제외한 나머지 항은 무시한다
  ex) O(n+3) = O(n)
  ex) O(n + logn) = O(n)
  
  

Big-O 표기법의 종류

O(1) - 상수 시간

데이터 증가와 상관없이 일정한 실행 시간을 가진다

O(logn) - 로그 시간

한 번 검색할 때마다 속도가 1/2로 줄어든다
실행 시간이 입력 크기의 로그에 비례한다
ex)이진 탐색

O(n) - 선형 시간

알고리즘 실행 시간이 입력 크기에 정비례한다
ex) 반복문

O(nlogn) - N 로그 시간 N

실행 시간이 입력 크기와 입력 크기의 로그 곱에 비례한다
ex)병합정렬, 퀵정렬, 힙정렬

O(n²) - 이차 시간

알고리즘의 실행 시간이 입력 크기의 제곱에 비례한다
ex) 2중 반복문, 버블정렬, 선택 정렬, 삽입 정렬

O(2ⁿ) - 지수 시간

입력 데이터들의 원소들로 만들 수 있는 모든 부분 집할을 생성한다
ex)피보나치수열

O(n!) - 계승 시간

입력 데이터의 원소들로 만들 수 있는 모든 순열을 생성한다
ex) 재귀함수, 팩토리얼