빅 오(Big - O) 표기법 이란?

빅 오(Big - O) 표기법

알고리즘의 시간 복잡도를 나타내는 표기법으로 쉽게 말하면 알고리즘 효율성을 표기해주는 표기법이다.

알고리즘 효율성은 데이터에 대한 연산 횟수를 의미하며, 빅오뿐만 아니라 빅 오메, 빅 세타가 표기법도 존재한다.

 

 점근 표기법

빅 오 표기법(Big-O) O(n)

- 알고리즘의 시간 복잡도의 상한(上限: upper bound)값

- 최악의 경우를 표현 (worst case)

 

빅 오메가 표기법(Big-Omega) Ω(n)

- 알고리즘의 시간 복잡도의 하한(下限: lower bound) 값

- 최고의 경우를 표현 (best case)

 

빅 세타 표기법(Big-Theta) θ(n)

- 알고리즘의 시간 복잡도의 상한 과 하한의 교집합

- 평균의 경우를 표현 (average case) * 빅 오 O(n)와 빅 오메가 Ω(n)의 교집합 느낌

 

셋 중 빅 오 표기법을 사용하는 이유?

  빅 오 표기법은 최악의 경우에 대한 표기법을 기준으로 하기 때문에 모든 경우가 해당 효율성 안에 들어오기 때문에

 

시간 복잡도

O(1) 상수 시간 : 입력 크기와 관계없이 고정된 시간으로 계산한다면 알고리즘이 상수 시간에 실행된다고 한다.

ex) 배열의 n번째 원소 접근, 스택에 push / pop, 큐에 offer / poll, 해시 테이블의 원소에 접근

 

O(log n) 로그 시간 : 알고리즘의 실행 시간이 입력 크기의 로그에 비례

ex) 이진 탐색

 

O(n) 선형 시간 : 알고리즘의 실행 시간이 입력 크기에 정비례

ex) 배열에서 검색, 최솟값, 최댓값 찾기 등 연산, 연결 리스트에서 순회, 최솟값, 최댓값 찾기 등 연산

 

O(n log n) N 로그 N 시간 : 알고리즘의 실행 시간이 입력 크기와 입력 크기의 로그 곱에 비례

ex) 병합 정렬, 퀵 정렬(평균, 최악은 O(n^2)), 힙 정렬

 

O(n^2) 2차 시간 : 알고리즘 실행 시간이 입력 크기의 제곱에 비례

ex) 버블 정렬, 선택 정렬, 삽입 정렬, 이중 for문

 

O(2n) 지수 시간 : 입력 데이터들의 원소들로 만들 수 있는 모든 부분 집합을 생성

ex) 피보나치수열