[알고리즘] 시간복잡도(Time Complexity)

이전 포스팅에서 알고리즘에 대한 개념을 설명했다.

그 중, 시간복잡도라는 개념이 나왔는데 밑의 그림을 예로 들었는데 이해가 쉬우리라 판단된다.

보이는 것처럼, "알고리즘"이 수행되는 시간이 시간복잡도이다.

비슷한 친구로 "공간복잡도" 라는 개념도 있는데, 반대로 "메모리"를 얼마나 사용하는지에 대한 용량의 개념이다.

데이터를 저장할 수 있는 메모리와 저장매체의 발전으로 인하여 메모리에 대한 개념 또한 그렇게 큰 범주가 되지 못하고 있다.

예컨데, 예전 프로그래밍에서 배열이나 동적할당을 최소화 하고 컴파일을 최소화하며.. 등등 메모리가 얼마 없던 시절의 최적화 하기 위한 행동들은

지금은 하지 않아도 된다. 다만, 최적화의 범주에서 볼 때 좋은 행동이라고 볼 수 있다.

시간복잡도의 그래프가 또 빠질 수 없는데, 예전에 쓴 포스팅에서 사골국물 끓이듯 다시 가져와본다.

바로 이것이 그 유명한 시간복잡도 그래프.

Big-O Complexity 라고 되어있는데, 이는 시간복잡도를 측정하기 위한 척도이다. 친구들이 2명이나 더 있는데 오메가, 세타 표기법이 있는데 잠시 후 언급예정.

보다시피 그래프가 수직으로 솟구치는 놈들도 있고, 거의 평행하게 드러누워 있는 놈들도 있다.

수직으로 솟구치는 놈들은 사용하지 마라! 라는 경고다

우리가 알고있는 순차탐색을 예로 들었을 때, 원소가 20개 존재한다고 하면 거의 시간복잡도가 없는 편이다. (n번 탐색)

반면에, 2^n이라던지 n! 같은 경운는 이미 안드로메다로 떠난지 오래다.

n = 20

n! = 2432902008176640000 (?ㅋㅋㅋㅋ)

...

2^n과 n^2 또한 언급할 필요가 없을 정도로 매우 크고 느리다.

시간복잡도가 빠른 순서대로 정리해보면 아래와 같다.

O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n) O(n!)

n!은 정말 최악

시간복잡도 표기법은 세가지가 있다

빅-오, 빅-오메가, 세타 표기법이 있는데 그래프를 먼저 보도록 하자

빅-오(O)

빅-오메가

세타(Θ)

이런식의 그래프가 존재한다.

딱 보기에 알아보기 쉬울 텐데, 정리하면 아래와 같다

빅-오 : 상한 점근(최악의 성능)

빅-오메가 : 하한 점근(최고의 성능)

세타 : 평균(빅-오와 빅-오메가의 평균)

주로 빅-오(O) 표기법을 사용한다. 이유는 알고리즘이 최악일 때 어떤 성능을 지녔는지 판단해야 평균과 가까운 성능을 예측할 수 있기 때문이다.

세타 표기법의 계산이 가능하다면 얼추 정확하고 좋겠지만, 빅-오 표기법 자체로도 알고리즘의 성능을 가늠할 수 있는 척도가 된다.

중요한건 "정확한" 성능이 아니다.

"얼추 이정도" 성능을 표기하는 방법이다.

데이터가 많아질 수록 이러한 추세로 성능이 나올 것이다. (그렇기 때문에 Asymptotic, 점근적 성능이라고 부른다.)

라는 개념의 복잡도 이므로, 무조건 n^2 혹은 n 의 성능이다! 라고 할 수 없는 것이다.

그래프의 시간복잡도

자료구조의 시간복잡도

정렬의 시간복잡도

힙의 시간복잡도

* 시간복잡도 정리 출처