Python 04. [Algorithm 01] 시간복잡도와 Big O

Big O

빅오 (O, big-O)

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

시간 복잡도 (Time Complexity)

어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도 (Computational Complexity)를 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 바로 빅오이다.

빅오 표기법의 종류

• \(O(1)\): 입력값이 아무리 커도 실행 시간은 일정함
  • 예: 해시 테이블의 조회 및 삽입
• \(O(log n)\): 웬만한 n의 크기에 대해서도 매우 견고함
  • 예: 이진 검색
• \(O(n)\): 알고리즘을 수행하는 데 걸리는 시간이 입력값에 비례하는 선형 시간 (Linear Time) 알고리즘
  • 예: 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우
• \(O(n log n)\): 대부분의 효율적인 정렬 알고리즘이 이 시간 복잡도를 가짐
  • 예: 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘, 팀소트 (Timsort)
• \(O(n^2)\): 버블 정렬 같은 비효율적인 정렬 알고리즘
• \(O(2^n)\): 피보나치 수를 재귀로 계산하는 알고리즘
• \(O(n!)\): 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제 (Travelling Salesman Problem)를 브루트 포스로 풀이할 때

실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느리다.

---

상한과 최악

• 복잡한 함수 \(f(n)\)이 있을 때, 빅오 표기법은 이 함수의 상한을 설명하는 방법이다.
  • 가장 빨리 실행될 때: 하한 (\(\Omega\))
  • 가장 늦게 실행될 때: 상한 (\(O\))

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

---

분할 상환 분석

분할 상환 분석 (Amortized Analysis)

동적 배열에서 더블링이 일어나는 일은 어쩌다 한 번뿐이지만, 이로 인해 지나치게 높은 시간 복잡도로 판단하는 것은 지나치게 비관적이다. 따라서 이 경우 ‘분할 상환’ 또는 ‘상각’이라고 표현하는, 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산할 수 있다.

---

병렬화

일부 알고리즘들은 병렬화로 실행 속도를 높일 수 있다. 알고리즘이 병렬화가 가능한지는 알고리즘의 우수성을 평가하는 척도 중 하나이다.