# 알고리즘 : 시간복잡도

컴퓨터공학을 전공한 학생이라면, 혹은 개발자로 근무하는 사람이라면 누구나 한번쯤은 들어보았을 용어가 있다.

빅오 (Big - O)

시간복잡도라는 것을 의미하는 내용인데, 프로그램 전체 혹은 특정 기능의 동작 소요 시간을 숫자화 하여 표현한 것을 뜻한다.

실제로 굉장히 중요한 의미를 갖는데, 정작 컴퓨터 공학을 갓 전공한 학생들의 대부분은 빅오가 뭐야? ~~내가 아는건 빅파이(노잼..)~~라는 생각으로 흘려보내는 경우가 많다.
솔직하게 말하면 본인도 지난번 N모 회사에서 면접을 진행하던 중 시간복잡도에 대한 질문공세에 정확하게 답변하지 못했다는 부끄러운 과거가 있다.

그.래.서.

이번 포스팅은 시간복잡도, 빅 오(Big O)에 대해서 한번 알아보도록 하자.

1. Why Using Big O?

프로그래머의 궁극적인 목표는
"빠르고, 정확하고, 편리한 프로그램을 구현하는 것 " 이다.
여기서 정확하다는 것은 오류가 존재하지 않는 것으로 판단할 수 있고, 편리하다는 것은 어느 사용자라도 메뉴얼 없이 프로그램 사용이 가능한 것으로 판단할 수 있다.

그렇다면 빠르다는 것은? 여기서 시간복잡도를 사용할 수 있다.

실제 시간복잡도가 완벽한 척도가 되지 못하는 경우도 있다.
하지만 수학적인 계산을 통하여 '꽤 신뢰할만한' 동작 소요 시간 값을 제공하기 때문에 많은 개발자들이 필수적으로 생각하고 참고하는 내용이기도 하다.

Algorithm is a series of contained steps which you follow in order to achieve some goal, or to produce some output.

알고리즘은 같은 내용을 구현한다 하더라도 다양한 모양과 형태로 구성된다.
결국 어떠한 형태를 갖느냐에 따라 매우 작은 시간복잡도를 가질수도, 혹은 불필요한 소요 시간을 가질 수도 있는 것이다.

2. Kind of Big O

Big-O notation is a way of converting the overall steps of an algorithm into algebraic terms, then excluding lower order constants and coefficients that don’t have that big an impact on the overall complexity of the problem.

시간복잡도에서 가장 중요한 부분은 '가장 높은 항', n의 단위이다.

고등학생때 lim가 기억난다면 이 부분은 쉽게 이해할 수 있을 것이다.

$O (1)$ 과 같은 상수(Constant) 형태

$O (\log n)$ 과 같은 로그(Logarithmic) 형태

$O (n)$ 과 같은 선형

$O (n \log n)$ 과 같은 선형로그 형태

$O (n^{c})$ , $O (n^{3})$ 과 같은 다차(Polynomial) 형태

$O (c^{n})$ , $O (3^{n})$ 과 같은 지수(Exponential) 형태

$O (n!)$ 과 같은 팩토리얼(Factorial) 형태

일반적으로 위로 갈수록 알고리즘이 매우 빨라지고, 아래로 갈수록 n의 값이 급격하게 커짐에 따라 알고리즘 수행 시간 또한 급격하게 증가한다.

위의 표는 다양한 시간 복잡도의 척도를 보여주고 있다.

위로 갈수록 간단하고, 아래로 갈 수록 복잡해진다.

여기서 logN은 지수로 2를 갖는 것을 의미한다(아마도 2진수를 의식하지 않았을까)

표를 자세히 보면 항상 n의 값이 적다고 해서 시간복잡도가 줄어들지는 않는다. (간혹 그런 경우가 존재하지만 대부분은 n의 값과 시간 복잡도는 반비례한다)

하지만 n의 값이 커질수록, 시간 복잡도가 복잡한 알고리즘은 수행시간이 급격하게 증가한다. 대표적으로 '정렬' 문제가 이에 해당한다. 일반적인 정렬은 O(n^2)과 같은 제곱의 형태가 되지만, quick 정렬과 같은 것을 사용하면 O(log)순으로 줄어드는 경우를 볼 수도 있다.

그렇다면 어떠한 경우에 어떠한 시간복잡도를 갖는 것일까?

가장 시간복잡도의 영향을 많이 받는 정렬의 경우에는 다음과 같다.

(참고 사이트 : http://blog.eairship.kr/35)

1. 버블 정렬 : O(n^2)

2. 삽입 정렬 : 최선의 경우 O(n), 최악의 경우 O(n^2), 평균 O(n^2)

3. 퀵 정렬 : 평균 O(nlogn), 최악 O(n^2)

C++에서 제공하는 sort 함수의 경우 퀵 정렬로 구현되어 있다고 한다.

참고 사이트

- 나무위키
: https://namu.wiki/w/시간%20복잡도

- (번역) 알고리즘 쉽게 이해하기: 시간 복잡도와 Big-O 표기
: https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/

- 누구나가 다 이해할 수 있는 프로그래밍 첫걸음 - 시간복잡도
: http://blog.eairship.kr/35

Joon's Blog