알고리즘, 계산 복잡도 이론, Big-O notation

CS (Computer Science)논문을 읽다보면 Big-O에 대한 이야기가 나온다.

특히, 이 글을 읽는 사람들 중에는 Deep learning의 인기덕분에 Neural Network 의 내부 연산과 가속 알고리즘에 대한 관심의 증가로 Big-O를 자주 접했을 것입니다.

하지만, CS 전공자가 아니면 Big-O와 시간복잡도가 친근하지 않아 어려움을 겪을것이라고 생각합니다.

조금이나마 도움이 됬으면 하는 마음에 작성합니다.

 

keywords = asymptotic notation, Big-O

1. Computational complexity theory (계산 복잡도 이론)
= 컴퓨터 과학(Computer Science)에서 계산이론(Theory of computation, 컴퓨터 과학의 한갈래)의 분야로, 계산문제를 푸는 알고리즘(Algorithm) 을 복잡도(complexity)에 따라 분류하여 문제의 모임을 구성하는 방법의 연구

2. 알고리즘 (Algorithm)이란? 
= 어떤 목적을 달성하거나 output을 뽑아내기 위해 거쳐야 하는 일련의 process
= 하나의 문제를 가지고 수백, 수천가지, 무한개의 Solution(algorithm) 이 존재

3. 시간복잡도
= input n 에 대하여 Algorithm이 문제를 해결하고 output을 내는 데 걸리는 시간
= Big-O의 표기를 이용하여 정의 가능
= 문제를 해결하는데 걸리는 시간과 입력(input) 의 함수 관계

3-1. 시간복잡도에서 중요한 것은 
= 정해진 표현식에 가장 큰 영향을 미치는 n 의 단위


4. 빅오(Big-O) 표기법 
= 알고리즘의 효율성을 표기해주는 표기법
= 상한선 기준으로 표기하기 때문에 대표성을 가짐 

(알고리즘 효율성은 값이 클수록 즉, 그래프가 위로 향할수록 비효율적임을 의미한다.)

 

4-1. 빅오(Big-O) 이외의 표기법
= 빅오메가는 하한선을 기준으로 표기

= 빅세타는 상한선과 하한선의 사이를 기준으로 표기

5. 빅오 표기법 특징
= 상수항 무시

= 영향력 없는 항 무시
ex) 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n0보다 크지 않은 모든 n에 대하여) 2n^4 + 3n의 식을 가진다면, 이 algorithm의 점근적(asymptotic) 시간 복잡도는 O(n^4)이라고 할 수 있다. 3n에 대한 복잡도는 무시한다. (Big-O는 점근적 표기법 이므로)

 

*점근적(asymptotic)

= 기존에는 멀리 있어 보이는 결과물이 근삿값에 점점 가까워지고 있는 상태

= 상수계수와 중요하지 않은 항목 제거하고 output에 큰 영향을 미치는 값만 고려

= 한마디로, 중요도가 높은거 위주로 (근사값)

O(1) = 상수 시간 : 정수가 짝수이거나 홀수인지 결정
O(log n) = 로그 시간 : 이진탐색(binary search algorithm)
O(n) = 선형 시간 : 정렬되지 않은 배열 (array)에서 가장 작은 수(min) 또는 가장 큰 수 (max)를 탐색
O(n^2) = 2차 시간 : Bubble sorted, Insertion sort
O(n^3) = 3차 시간 : 행렬곱셈(matrix multiplication)


보다 자세한 내용은 아래 출처를 참고하여 공부하면 될거 같습니다.

출처: 
https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84
https://noahlogs.tistory.com/27