빅오, 자료형

컴퓨터 과학에서 빅오(Big-O)는 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구 사항(공간 복잡도)이 어떻게 증가하는지를 분류하는 데 사용 되며, 알고리즘의 효율성을 분석하는 데에도 매우 유용하게 활용된다.

먼저, 빅오는 점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기 방법 중 하나로 점근적 실행 시간이란 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 lim 함수의 실행 시간의 추이를 의미한다. 알고리즘은 궁극적으로는 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다. 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다.

점근적 실행 시간은 달리 말하면 시간 복잡도라 할 수 있다. 시간 복잡도(Time Complexity)의 사전적 정의는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational complexity)를 의미하며 계산 복잡도를 표기하는 대표적인 방법이 바로 빅오다. 빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며, 계수는 무시한다. 예를 들어 입력값 n에 대해

번 만큼 계산하는 함수가 있다면 이 함수의 시간 복잡도는 최고 차항만 고려하고 이 중에서도 계수는 무시해 만을 고려 한다. 즉 여기서의 시간 복잡도는 O(n**2)이 된다. 이처럼 시간 복잡도를 표기할 때는 입력값에 따른 알고리즘의 실행 시간의 추이만을 살피게 된다.

실행 시간의 추이에 따른 빅오 표기법
- O(1) : 입력값이 아무리 커도 실행 시간은 일정하다. 최고의 알고리즘이라 할 수 있다. 상수 시간을 갖는 알고리즘은 성배와 같아서 찾을 수만 있다면 놀라울 정도로 가치가 있지만, 현실적으로 어려움이 따른다. 또 한 상수 시간에 실행된다 해도 상수값이 상상을 넘어설 정도로 매우 크다면 사실상 일정한 시간의 의미가 없다. 최고의 알고리즘이 될 수 있지만 그만큼 신중해야한다. O(1)에 실행되는 알고리즘으로 해시 테이블의 조회 및 삽입이 이에 해당한다.
- O(log n) : 실행 시간은 입력 값에 영향을 받는다. 그러나 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 웬만한 n의 크기에 대해서도 매우 견고하다. 대표적으로 이진 검색이 이에 해당한다.
- O(n) : 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간(Linear-Time)알고리즘이라고한다. 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우가 이에 해당하며 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴봐야 한다.
- O(n log n) : 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 (O n log n)보다 빠를 수 없다. 물론 입력 값이 최선인 경우, 비교를 건너뛰어 O(n)이 될 수 있다.
- O(n2)** : 버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.
- O(2n)** : 피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다.
- O(n!) : 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때가 이에 해당하며 가장 느린 알고리즘으로 입력값이 조금만 커져도 웬만한 다항 시간 내에는 계산이 어렵다.

빅오는 시간 복잡도 외에도 공간 복잡도를 표현하는 데에도 널리 쓰인다. 또 한 알고리즘은 흔히 ‘시간과 공간이 트레이드 오프(Space-Time Tradeoff)’관계라고도 하는데 이 말은 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고,
공간을 적게 사용하는 알고리즘은 실행 시간이 느리다는 얘기다.

물론 실행 시간이 빠르면서도 공간을 적게 차지하는 알고리즘이 존재하지만 대부분의 경우 시간과 공간은 트레이드오프 관계이며 이는 알고리즘의 주요한 특징 중 하나이다.

상한과 최악평균적인 시간보다는 상한 시간으로 단순화하여 주로 표현하는데, 매번 구분하는것이 번거롭고 혼동되기도 하며 상한으로만 표현하는 방법이 틀리지 않기 때문이기도 하다.
여기서 한 가지 중요한 점은 상한을 최악의 경우와 혼동하는 것인데, 빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 ‘적당히 정확하게’ 표현하는 방법일 뿐, 최악의 경우,평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념이라는 점에 유의해야한다.
빅오(O)는 상한(Upper Bound)을 의미한다. 이외에도 하한(Lower Bound)을 나타내는 빅오메가, 평균을 의미하는 빅세타가 있는데, 학계와 달리 업계에서는 빅세타와 빅오를 하나로 합쳐 단순화해 표현하려는 경향이 있다.
분할 상환 분석따라서 이 경우 ‘분활 상환’ 또는 ‘상각’ 이라고 표현하는, 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산할 수 있다. 이렇게 할 경우 동적 배열의 삽입 시 시간 복잡도는 O(1)이 된다.
분할 상환 분석(Amortized Analysis)은 빅오와 함께 함수의 동작을 설명할 때 중요한 분석 방법 중 하나로 분할 상환 분석이 유용한 대표적인 예로 ‘동적 배열’을 들 수 있는데, 동적 배열에서 더블링이 일어나는 일은 어쩌다 한 번 뿐이지만, 이로 인해 ‘아이템 삽입 시간 복잡도는 O(n)이다’ 라고 확정짓는건 지나치게 비관적이고 정확하지도 않다.
병렬화GPU는 결국 같은 시간에 훨씬 더 많은 연산을 할 수 있기 때문에 딥러닝 알고리즘을 비롯해 병렬 연산이 가능한 알고리즘들은 최근에 큰 주목을 받고 있다. 알고리즘 자체의 시간 복잡도 외에도 알고리즘이 병렬화가 가능한지는 근래에 알고리즘의 우성을 평가하는 매우 중요한 척도 중 하나이기도 하다.
일부 알고리즘들은 병렬화로 실행 속도를 높일 수 있다. 딥러닝의 인기와 함께 병렬화가 큰 주목을 받고 있으며 GPU는 병렬 연산을 위한 대표적인 장치이기도 하다.

스타일 가이드
styleguide
python 가이드 라인
Welcome to Python.org

Welcome to Python.org

The official home of the Python Programming Language

www.python.org