시간복잡도(Time Complexity) 란?

시간 복잡도란?

특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다.

같은 결과를 가져오는 프로그램도 어떻게 작성하느냐에 따라 걸리는 시간이 달라집니다.

같은 결과를 나타내는 소스라면 최대한 시간이 적게 걸리는 소스가 좋은 소스입니다.

그렇기에 더 효율적인 알고리즘을 구성하기 위해서 시간 복잡도의 측면을 고려하고 중요하게 봅니다.

 

빅 - 오 표기법이란?

시간 복잡도에는 여러 개념이 있지만, 그 중 '아무리 많이 걸려도 이 시간 안에는 끝날 것'의 개념이 제일 중요하다.

최악의 경우를 발생을 예측하고, 이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라고 부른다.

O(1)  (constant time)

: 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 말한다.

데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않는다.

O(logN) (log time)

: 입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아지는 알고리즘이다.

Ex. 데이터가 10배가 되면, 처리 시간은 2배가 된다. 이진 탐색이 대표적이며 재귀가 순기능으로 이루어지는 경우도 해당된다.

O(n) (linear time)

: 입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘이다.

Ex. 데이터 10배가 되면, 처리 시간도 10배가 된다. (1차원 for문)

O(NlogN) (log linear time)

: 데이터가 많아질수록 처리시간이 로그 배만큼 더 늘어나는 알고리즘이다.

Ex. 데이터가 10배가 되면, 처리시간은 약 20배가 된다. 정렬 알고리즘 중 병합,퀵이 대표적이다.

O(n²) (quadratic time)

데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘이다.

Ex. 데이터가 10배가 되면, 처리시간은 최대 100배가 된다. (2중 반복문)

단, m이 n보다 작을 때는 반드시 O(nm)으로 표시하는 것이 바람직하다.

O(2ⁿ) (exonential)

: 데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘이다.

Ex. 피보나치 수열, 재귀 역기능

 

시간 복잡도를 줄이는 방법은?

- 반복문이 가장 시간 소모가 크니, 반복문 숫자를 줄이는 것이 줄이는 방법이다.

- 자료구조를 적절하게 이용하는 방법 ( 각 자료구조에 대한 시간 복잡도가 잘 나와 있다. )

- 알고리즘을 적절하게 이용하는 방법 ( 각 알고리즘마다 시간복잡도 효율이 좋은 게 있다. )