시간 복잡도를 표기하는 방법 중 하나인 Big O 표기법에 대해 정리해본다.
시간 복잡도
알고리즘의 시간 복잡도는 입력을 나타내는 문자열 갈이의 함수로서 작동하는 알고리즘을 취해 정량화하는 것을 의미한다.
시간 복잡도는 기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다.
주로 계수와 낮은 차수를 제외시키는 방법인 Big O 표기법을 통해 나타내며, 이 방식으로 표현할 때 점근적으로 묘사한다고 말한다.
점근 표기법
점근 표기법은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법으로 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰이며, 대표적으로 다섯 가지 표기법이 존재한다.
-
Big-O : [상한 점근] 최악의 경우를 기준으로 표기
-
little-o : Big-O 보다 엄격한 기준으로 표기
-
Big-Ω : [하한 점근] 최선의 경우를 기준으로 표기
-
little-⍵ : Big-Ω 보다 엄격한 기준으로 표기
-
Big-Θ : [상한/하한 점근] 평균의 경우를 기준으로 표기
Big O notation
Big-O 표기법은 최악의 경우를 기준으로 시간 복잡도를 표기하기 때문에 해당 알고리즘이 최소한 어느정도의 효율을 보이는지 알 수 있다, 이 때문에 Big-O 표기법이 많이 사용되고 있다.
특징
- 상수항, 계수 생략 : 계수 법칙, 합의 법칙, 곱의 법칙 등의 규칙에 의해서 입력 크기가 어느정도 크고, 입력크기와 연관이 없을 때 상수항을 생략하거나, 계수를 생략할 수 있다. ex) O(n+5) = O(n), O(5n) = O(n)
- 최고차항 외에 생략 : 다항 법칙에 의해 최고차항 외에는 생략할 수 있다. ex) O(4n^3+2n^2+n) = O(n^3)
종류
O(1)=>O(log n)=>O(n)=>O(n log n)=>O(n^2)=>O(2^n)
O(1)=>O(2^n) 순으로 느리다
-
O(1) : 입력값과 상관없이 일정한 연산 스탭을 가지는 알고리즘이 해당
(스택에서의 push, pop)
-
O(log n) : 입력값을 반씩 나눠서 크기를 줄여가며 연산하는 알고리즘이 해당
(이진트리등 이진 알고리즘)
-
O(n) : 입력값에 따라 연산 스탭이 선형적으로 증가하는 알고리즘이 해당
(for문)
-
O(n log n) : 입력값 n을 log2 n으로 나누는 연산을 가진 알고리즘이 해당
(퀵정렬, 병합정렬, 힙정렬)
-
O(n^2) : 내부에서 연산을 중첩적으로 실행하는 알고리즘이 해당
(이중 for문, 삽입정렬, 거품정렬, 선택정렬)
-
O(2^n) : 재귀함수 등 스스로 재귀적인 알고리즘이 해당
(피보나치 수열)
참고 사이트
위키백과-점근표기법
위키백과-시간 복잡도
velog-2seunghye-[자료구조.알고리즘] 빅오표기법(Big-O notation)
tistory-인생의 로그캣-빅오 표기법(big-O notation) 이란
