빅오

📖 빅오(O, big-O)란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다.

빅오는 점근적 실행 시간을 표기할 때 쓰이는 표기법이다.

• 점근적 실행 시간(Asymptotic Running Time): 입력값 n이 커질 때, 즉 무한대를 향할 때 함수의 실행 시간의 추이를 의미

충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다.

점근적 실행 시간은 달리 말하면 시간 복잡도라 할 수 있다.

• 시간 복잡도(Time Complexity): 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity)를 의미

빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며, 계수는 무시한다.

종류는 크게 다음과 같다.

• O(1)
  • 입력값이 아무리 커도 실행 시간을 일정하다.
  • 해시 테이블의 조회 및 삽입이 이에 해당한다.
• O(log n)
  • 매우 큰 입력값에도 크게 영향을 받지 않는 편이다.
  • 이진 검색이 이에 해당한다.
• O(n)
  • 입력값만큼 실행 시간에 영향을 받으며, 수행 시간이 입력값에 비례한다. (Linear-Time 알고리즘)
  • 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우가 이에 해당한다.
• O(n log n)
  • 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다.
  • 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 O(n log n)보다 빠를 수 없다. 물론 입력값이 최선인 경우, 비교를 건너뛰어 O(n)이 될 수 있다.
• O(n^2)
  • 버블 정렬같은 비효율적인 정렬 알고리즘이 이에 해당한다.
• O(2^n)
  • 피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다.
  • n^2보다 n^2이 훨씬 크다.
• O(n!)
  • 각 도시를 방문하고 돌아오는 가장 짧은 경로는 찾는 외판원 문제(Travelling Salesman Problem, TSP)를 브루트 포스로 풀이할 때가 이에 해당한다.
  • 가장 느린 알고리즘으로 입력값이 조금만 커져도 시간 내에 계산이 어렵다.
    
    

빅오는 시간 복잡도 외에도 공간 복잡도를 표현하는 데에도 쓰인다.

또한 알고리즘은 흔히 ‘시간과 공간이 트레이드오프(Space-Time Tradeoff)’ 관계다.

실행 시간이 빠르면서도 공간을 적게 차지하는 알고리즘이 드물게 존재하지만,

대부분의 경우 시간과 공간은 트레이드오프 관계이며 이는 알고리즘의 주요 특징 중 하나다.

상한과 최악

빅오(O)는 상한(Upper Bound)을 의미한다.
이외에도 하한(Lower Bound)을 의미하는 빅오메가(Ω), 평균을 의미하는 빅세타(Θ)가 있다.

상한을 최악의 경우와 혼동하는 경우가 있는데, 빅오 표기법은 표기법일 뿐,
‘주어진(최선/최악/평균) 경우’와는 아무런 관계가 없는 개념이다.

빅오를 비롯한 점근 표기법은 함수 f(n)이 있을 때, 이 함수의 실행 상한과 하한을 의미한다.
즉 가장 늦게 실행될 때를 빅오(O), 가장 빨리 실행될 때를 빅오메가(Ω), 평균적으로는 빅세타(Θ)로 지칭한다.
n이 작은 경우는 무시하며, 빅오 표기법은 n이 매우 클 때의 전체적인 큰 그림에 집중한다.

정리해보자면 빅오 표기법은 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다.

분할 상환 분석

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

분할 상환 분석(Amortized Analysis)은 빅오와 함께 함수의 동작을 설명할 때 중요한 분석 방법 중 하나다.

• ‘분할 상환’ 또는 ‘상각’: 최악의 경우를 여러 번의 걸쳐 골고루 나눠주는 형태

대표적인 예로 동적 배열에서 더블링이 일어나는 일은 어쩌다 한 번뿐이지만,
이로 인해 ‘아이템 삽입 시 시간 복잡도는 O(n)이다.’라고 얘기하는 건 지나치게 비관적이고 정확하지도 않다.

분할 상환으로 알고리즘의 시간 복잡도를 계산할 경우 동적 배열의 삽입 시 시간 복잡도는 O(1)이 된다.

최근에는 시간 복잡도를 분석할 때 보편적으로 사용되는 방법이다.

병렬화

일부 알고리즘들은 병렬화로 실행 속도를 높일 수 있다.

GPU는 병렬 연산을 위한 대표적인 장치로, 각각의 코어는 CPU보다 훨씬 느리지만 수천여 개로 구성되어 있어 CPU보다 수백 배 더 많은 연산을 동시에 수행할 수 있다.

그래서 딥러닝 알고리즘을 비롯해 병렬 연산이 가능한 알고리즘들이 최근에 큰 주목을 받았다.

시간 복잡도 외에도 병렬화 가능 여부가 근래에 알고리즘의 우수성을 평가하는 척도 중 하나이다.

---

출처: 박상길. 파이썬 알고리즘 인터뷰 - 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트.