빅 오(Big-O)는 알고리즘을 다루는 거의 모든 책에서 상세히 다루는 주제 중 하나다.
빅오는 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구사항(공간 복잡도)이 어떻게 증가하는지를 분류하는데 사용된다.
빅 오는 점근적 실행 시간를 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나다. 점근적 실행시간이란 입력값 n이 커질 때 즉 입력값이 무한대를 향할때 lim(n->무한대) 함수의 실행 시간의 추이를 의미한다. 알고리즘은 궁극적으로는 컴퓨터로 구현되므로 컴퓨터의 빠른 처리 능력을 감안하면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다. 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다.
시간 복잡도(Time Complexity)
어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity)를 의미한다.
계산 복잡도를 표기하는 대표적인 방법이 바로 빅오다.
빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며, 계수는 무시한다.
O(1)
최고의 알고리즘.
입력값이 아무리 커도 실행 시간은 일정하다.
상수 시간을 갖는 알고리즘으로 해시 테이블의 조회 및 삽입이 이에 해당한다.
O(logN)
실행시간은 입력값에 영향을 받는다.
로그는 매우 큰 입력값에도 크게 영향력을 받지 않는 편으로 웬만한 n의 크기에 대해서도 매우 견고하다.
대표적으로 이진 검색이 이에 해당한다.
O(n)
선형 시간(Linear-Time) 알고리즘.
입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다.
정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우
모든 입력값을 적어도 한 번 이상 살펴봐야 한다.
O(n log N)
적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘
아무리 좋은 알고리즘도 O(n log N)보다 빠를 수 없다.
병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘.
입력값이 최선인 경우, 비교를 건너뛰어 O(n)이 될수 있으며 팀소트(Timsort)가 이런 로직을 갖고 있다.
O(n^2)
버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.
O(2^n)
피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다.
간혹 n^2과 혼동하는 경우가 있는데, 처음에는 비슷해 보이지만 2^n이 훨씬 더 크다.
O(n!)
가장 느린 알고리즘.
각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제(TSP, Travelling Salesman Problem)를 브루트 포스로 풀이할 때가 이에 해당한다.
입력값이 조금만 커져도 웬만한 다항시간 내에는 계산이 어렵다.
상한과 최악
상한: 빅오가 의미한다.
하한: 빅오메가
평균: 빅세타
빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 적당히 정확하게 표현하는 방법일 뿐, 최악의 경우 평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념이라는 점에 유의해야 한다.
분할 상환 분석(Amortized Analysis)
빅 오와 함께 함수의 동작을 설명할 때 중요한 분석 방법 중 하나.
분할 상환 분석이 유용한 대표적인 예로는 동적 배열을 들 수 있다. 동적 배열에서 더블링이 일어나는 일은 어쩌다 한 번 뿐이겠지만, 이로 인해 아이템 삽입 시간 복잡도는 O(n)이다라고 얘기하는 건 지나치게 비관적이고 정확하지 않다.
병렬화
일부 알고리즘들은 병렬화로 실행 속도를 높일 수 있따.
최근엔 딥러닝의 인기와 함께 병렬화가 큰 주목을 받고 있으며, GPU는 병렬 연산을 위한 대표적인 장치이기도 하다.
GPU 각각의 코어는 CPU보다 훨씬 더 느리지만 GPU의 코어는 수천여 개로 구성되어 있어, 많아봐야 수십여개에 불과한 CPU보다 수백배 더 많은 연산을 동시에 수행할 수 있다.