빅오(O, big-O)
목차
intro
매우 중요한 주제 중 하나.
비용이 적게 드는 알고리즘을 위해 효율성 분석 (performance analysis) 필요
시간(time complexity) 과 비용(연산하는데 필요한 시간과 기억장소 space complexity)을 줄이는 분석 방법
- 하드웨어의 발달로 사용 메모리 크기에 관한 공간 복잡성의 중요도는 낮아짐
사용하는 곳
- 컴퓨터과학에서 빅오는 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구사항(공간 복잡도)이 어떻게 증가하는지를 분류하는 데 사용됨
- 알고리즘의 효율성을 분석하는 데에도 매우 유용하게 활용된다.
의의
입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법.
점근적 실행 시간(Asymptotic Running Time)를 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나.
EX) \(f(n) = O(n)\)로 표시가 되었다면, 우리는 이것을 \(f(n)\)의 차수(order) 가 n 이라고 하며,
‘Big-Oh of n’ 이라고 읽는다.
[점근적 실행 시간]
입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 \(lim_x->∞\) 함수의 실행 시간의 추이를 의미.
점근적 실행 시간 = 시간 복잡도(Time Complexity)
- 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도Computational Complexity 를 의미
- 계산 복잡도를 표기하는 대표적인 방법이 바로 빅오
- 빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며, 계수는 무시
(ex) [입력값 n에 대해 \(4n^2 +3n+4\)번만큼 계산하는 함수]
\(n^2\) 만 고려
여기서의 시간 복잡도는 O(n^2 )
- 시간 복잡도를 표기할 때는 입력값에 따른 알고리즘의 실행 시간의 추이만을 살핌
표기법 종류
시간 복잡도를 표기할 때는 입력 값에 따른 알고리즘의 실행 시간의 추이만을 살피게 된다. 이 추이에 따른 빅오 표기법의 종류는 크게 다음과 같다.
탐색
주어진 원소들 중에서 어떤 특정한 원소를 찾는 것임
탐색의 2 가지 방법
1) 순차 탐색 (sequential search)
원소들이 정렬되어 있지 않을 경우에 원소들을 처음부터 차례로 비교하여 찾는 것임
2) 이진 탐색 (binary search)
원소들이 정렬되어 있는 상태에서 어느 특정 원소를 찾는 방법으로 순차탐색 보다 빠름
O(1)
- 입력값이 아무리 커도 실행 시간은 일정.
- 최고의 알고리즘. ( -> 찾기 매우매우 힘듦)
- 또한 상수 시간에 실행된다 해도 상수값이 상상을 넘어설 정도로 매우 크다면 사실상 일정한 시간의 의미X.
O(\(log_{2}n\))
- 여기서부터 실행 시간은 입력값에 영향 받음.
- 그러나 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편
-> 웬만한 n의 크기에 대해서도 매우 견고. - 이진탐색(binary search)
- 분할 정복 알고리즘 (divide and conquer algorithm)
O(n)
- 선형탐색 Linear search 알고리즘: 모든 원소를 조사하는 탐색
- 순차 탐색은 배열에 있는 특정한 원소를 찾기 위하여 배열의 처음 원소부터 차례로 모든 원소들을 비교하여 탐색함
- 입력값만큼 실행 시간에 영향을 받음
- 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례.
- (ex) 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우
-> 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴봐야 함
O(\(nlog_{2}n\))
- 병합 정렬(17장 참조)을 비롯한 대부분의 효율 좋은 정렬 알고리즘.
- 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(n log n)보다 빠를 수 없음.
O(\(n^2\))
- 정렬알고리즘
- 임의로 나열되어 있는 데이터들을 주어진 항목에 따라 크기 순서대로 작은 순서부터 (오름차순) 또는 큰 순서부터 (내림차순) 늘어놓은 것임
- 정렬되어 있는 데이터들은 다음과 같은 작업을 수행할 때 응용 ① 데이터를 탐색할 때 ② 리스트에 있는 다른 항목들을 비교할 때
- 대표적인 정렬 알고리즘: 버블 정렬(bubble sort), 삽입 정렬(insert sort), 선택 정렬(Select sort)
O(\(2^n\))
- 피보나치 수 재귀로 계산하는 알고리즘.
O(n!)
- 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제 Travelling Salesman Problem (이하 TSP)를 브루트 포스로 풀이할 때
- 가장 느린 알고리즘으로, 입력값이 조금만 커져도 웬만한 다항 시간 내에는 계산이 어려움
빅오는 시간 복잡도 외에도 공간 복잡도를 표현하는 데에도 널리 쓰임
- 알고리즘은 흔히 ‘시간과 공간이 트레이 드오프 Space-Time Tradeoff ’ 관계
- 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느림
상한과 최악
빅오 표기법은 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다
최선 ↔ 평균 ↔ 최악
탐색 알고리즘의 수행 시간은 입력 집합에 따라 다를 수 있다.
- 최선의 경우(best case): 수행 시간이 가장 빠른 경우
- 평균의 경우(average case): 수행시간이 평균적인 경우
-
최악의 경우(worst case): 수행 시간이 가장 늦은 경우
- 빅오(O): 상한(Upper Bound) 을 의미.
- 최악의 경우(worst case): 수행 시간이 가장 늦은 경우
- 빅오메가 (Ω): 하한 Lower Bound 을 나타냄
- 최선의 경우(best case): 수행 시간이 가장 빠른 경우
- 빅세타(Θ): 평균을 의미
- 평균의 경우(average case): 수행시간이 평균적인 경우
- 평균의 경우(average case): 수행시간이 평균적인 경우
사용
- 최선의 경우: 의미가 없는 경우가 많다.
- 평균적인 경우: 계산하기가 상당히 어려움.
- 최악의 경우: 가장 널리 사용된다. 계산하기 쉽고 응용에 따라서 중요한 의미를 가질 수도 있다.
-> 즉 최악의 경우를 가정하고 알고리즘을 짠다
학계와 달리 업계에서는 빅세타와 빅오를 하나로 합쳐서 단순화해서 표현하려는 경향이 있음.
평균적인 시간보다는 상한 시간으로 단순화해서 주로 표현하는데, 매번 구분하는 것이 번거롭고 혼동되기도 하며 또한 상한으로만 표현하는 방 법이 틀리지 않기 때문이기도 하다.
주의점
표기법은 정확 하게 쓰기에는 너무 길고 복잡한 함수를 ‘적당히 정확하게’ 표현하는 방법일 뿐,
최악의 경우/평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념이라는 점에 유의해야 함
복잡한 함수의 빅 오 표기
밑의 그림과 같이 복잡한 함수 f(n)이 있을 경우, 이 함수의 실행 상한과 하한을 의미. 
즉 가장 빨리 실행될 때(하한), 가장 늦게 실행될 때(상한)를 뜻함
이 중 가장 늦게 실행될 때를 빅오(O), 가장 빨리 실행될 때를 빅오메가(Ω), 평균적으로는 빅세타(Θ)로 지칭한다.
n이 작을 때, 즉 n_0 이하일 때의 값이 작은 경우는 무시하며, 빅오 표기법은 n이 매우 클 때의 전체적인 큰 그림에 집중한다
분할 상환 분석 Amortized Analysis
[등장 배경] 시간 또는 메모리를 분석하는 알고리즘의 복잡도를 계산할 때, 알고리즘 전체를 보지 않고 최악의 경우만을 살펴보는 것은 지나치게 비관적이라는 이유로 등장
[의의] 빅오와 함께 함수의 동작을 설명할 때 중요한 분석 방법 중 하나.
- (유용하게 쓰이는 예)
- ‘동적 배열’
- 동적 배열에서 더블링이 일어나는 일은 어쩌다 한 번뿐이지만, 이로 인해 ‘아이템 삽입 시시간 복잡도는 O(n)이다.’라고 얘기하는 건 지나치게 비관적이고 정확하지도 않음 -> 이 경우 ‘분할 상환’ 또는 ‘상각 償却 ’이라고 표현하는, 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산할 수 있다. 이렇게 할 경우 동적 배열의 삽입 시 시간 복잡도는 O(1)이 된다.
병렬화
(유용하게 쓰이는 예)
- 딥러닝의 인기와 함께 병렬화가 큰 주목을 받고 있음
- GPU는 병렬 연산을 위한 대표적인 장치
GPU 각각의 코어는 CPU보다 훨씬 더 느리지만
GPU의 코어는 수천여 개로 구성되어 있어, 많아 봐야 수십여 개에 불과한 CPU보다 수백 배 더 많은 연산을 동시에 수행가능
-> GPU는 결국 같은 시간에 목적지에 훨씬 더많은 짐을 나를 수 있다.