빅오(big-O), 분할 상한 분석

빅오 : 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법.

 

입력값 n이 무한대를 향할 때 함수의 실행 시간 추이를 의미하는 점근적 실행 시간을 표기할 때 가장 널리 쓰인다.

 

 

 

위 그래프에서 시간 복잡도 O(1)의 경우, 입력값 n이 아무리 커져도 시간은 같다. 즉, 데이터의 크기가 아무리 커져도 처리하는 시간은 변함이 없다는 것! 최고의 알고리즘이라 할 수 있지만 이러한 경우는 거의 드물다. 알고리즘 중에서는 테이블의 조회 및 삽입이 이에 해당한다.

 

O(logn)의 경우, 실행 시간은 입력값에 적은 영향을 받는다(받긴 받는다!). 대표적으로 이진 검색이 이에 해당한다.

 

O(n)의 경우, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. 선형 시간 알고리즘이라고도 하며, 정렬되지 않은 리스트에서 최댓값, 최솟값을 찾는 경우가 이에 해당한다.

 

O(nlogn)의 경우, 병합 정렬같은 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 적어도 모든 수에 대해 한 번 이상 비교해야 하는 비교 기반 정렬 알고리즘은 O(nlogn) 보다 빠를 수 없다. 다만 입력값이 최선인 경우, 비교를 건너뛰어 O(n)이 될 수 있으며 팀 소트(timsort)가 이러한 로직을 갖고 있다.

 

O(n^2)의 경우, 버블 정렬같은 비효율 정렬 알고리즘이 이에 해당한다.

 

O(2^n)의 경우, 피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다. 간혹 n^2과 혼동하는 경우가 있는데 n이 커지다 보면 2^n이 훨씬 더 크다.

 

마지막으로 O(n!)의 경우, 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때(...?)가 이에 해당한다. 가장 느린 알고리즘으로, 입력값이 조금만 커져도 웬만한 다항 시간 내에는 계산이 어렵다.

 

 

적절한 시간과 공간을 사용하는 것이 중요하다

 

알고리즘에서 시간과 공간은 trade-off 관계이기 때문에, 실행 시간이 빠르면 공간을 많이 사용하고 아니면 그 반대가 될 수 있다. 이는 알고리즘의 주요한 특징 중 하나이다.

 

분할 상환 분석 : 시간 or 메모리를 분석하는 알고리즘의 복잡도를 계산할 때, 알고리즘 전체를 보지 않고 최악의 경우만을 살펴보는 것은 지나치게 비관적이라는 이유로 이 방법이 등장하게 되었다.

 

대표적인 예로 '동적 배열'을 들 수 있다. 동적 배열에서 더블링이 일어나는 일은 어쩌다 한 번뿐이지만, 이로 인해 시간 복잡도를 O(n)이라고 얘기하는 것은 지나치게 비관적이고 정확하지도 않다. 따라서 이 경우, '분할 상환' 혹은 '상각'이라고 표현하는, 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산할 수 있다. 이렇게 할 경우 동적 배열의 시간 복잡도는 O(1)이 된다.

 

병렬화 : 최근에 딥러닝의 인기로 병렬화가 큰 주목을 받고 있다. GPU는 병렬 연산을 위한 대표적인 장치인데 GPU는 CPU에 비해 각각의 코어는 느리지만 훨씬 많은 코어를 갖고 있다. 따라서 이러한 GPU의 특성을 제대로 이용한 알고리즘은 속도 면에서 CPU로 동작하는 같은 알고리즘 대비 우수하다고 할 수 있다. 그러하여 알고리즘의 병렬화 여부가 근래에는 알고리즘의 우수성을 평가하는 중요한 척도 중 하나가 되었다.

 

 

 

 

 

출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]