[22.03.08] 빅오 표기법

 

# 백준 문제를 풀다 구글링을 할 때 등장하던 시간 복잡도 표기 방법!!

 

알고리즘의 연산들이 몇 번이나 수행되는지를 숫자로 표시한 '시간 복잡도' T(n)

- 대입연산, 덧셈연산, 곱셈연산 등 연산이 몇번 이루어진지를 합해 표현한다

 

빅오 표기법 : 연산의 횟수를 대략적으로 표기한 것

자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시된다.

 

두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n >= n_0에 대하여 |f(n)| <= c|g(n)|을 만족하는 2개의 상수 c, n_0가 존재하면 f(n) = O(g(n))이다.

 

ex)

f(n) = 5 일 경우 O(1): n_0 = 1, c = 10이면 n >= 1에 대하여 5 <= 10x1이 됨

 

f(n) = 2n+1이면 O(n): n_0 = 2, c =3이면 n >= 2 에 대하여 2n+1 <= 3n이 됨

 

계수를 제외한 최고차항을 표기한다고 생각하면 될 것 같다!!

 

O(1) : 상수형 (스택)

O(logn) : 로그형 (이진탐색)

O(n) : 선형 (for문)

O(nlogn) : 선형로그형 (퀵,병합,힙 정렬) # 대부분 효율이 좋다

O(n^2) : 2차형 (이중 for문, 삽입, 버블, 선택 정렬) # 비효율적이다

O(n^3) : 3차형

O(2^n) : 지수형 (피보나치 수열 - 재귀 계산) # n^2보다 큼

O(n!) : 팩토리얼형 # 가장 느린 알고리즘

 

 

이외에 하한선을 표기하는 빅오메가 표기법과 하한과 상한을 동시에 표시해 평균을 나타내는 빅세타 표기법도 존재한다