[파이썬 알고리즘 인터뷰] 4장 - 빅오 (big-O)

시작에 앞서 이 글은 박상길 저자님의 파이썬 알고리즘 인터뷰 책을 읽고 정리한 내용임을 밝힙니다. 

 

빅오 (O, big-O)

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

점근적 실행 시간 (Asymptotic Running Time)을 표기할 때 쓰이는 수학적 표기 방법입니다. 

빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기합니다. 

 

점근적 실행 시간 (Asymptotic Running Time)

점근적 실행 시간이란 입력값 n이 커질 때 (무한대를 향할 때) 실행 시간의 추이를 의미합니다. 

점근적 실행 시간은 다른 말로 시간 복잡도 (Time Complexity)라고 합니다. 

---

빅오 표기법의 종류

• O(1) :
  • 입력값이 아무리 크든 작든 실행 시간이 일정한 알고리즘입니다.
  • ex) 해시 테이블의 조회 및 삽입
    ㅤ
• O(log n) :
  • 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 알고리즘입니다.
  • 실행 시간이 입력값에 영향을 받긴 하지만, 그 영향이 크지는 않습니다.
  • ex) 이진 검색
    ㅤ
• O(n) :
  • 입력값만큼 실행 시간에 영향을 받는 알고리즘입니다.
  • 알고리즘 수행 시간이 입력값에 비례합니다.
  • 선형 시간 (Linear-Time)알고리즘이라고 합니다.
  • ex) 리스트에서 최댓값 또는 최솟값을 찾는 경우 
    ㅤ
• O(n log n) :
  • 대부분의 효율 좋은 알고리즘이 이에 해당합니다.
  • ex) 병합 정렬, 팀소트 (Timsort)
    ㅤ
• O(n²) :
  • 입력값에 따라 실행 시간이 기하급수적으로 증가하며, 비효율적인 정렬 알고리즘이 이에 해당합니다.
  • ex) 버블 정렬     
    ㅤ
• O(2ⁿ) :
  • O(n²)보다 입력값에 따라 실행 시간이 기하급수적으로 증가하며, 재귀 계산 알고리즘이 이에 해당합니다.
  • ex) 피보나치 수를 재귀로 계산하는 알고리즘
    ㅤ
    
• O(n!) :
  • 가장 느린 알고리즘으로 입력값에 따라 실행 시간이 가장 기하급수적으로 증가하는 알고리즘입니다.
  • ex) 외판원 문제 (Travelling Salesman Problem - TSP)
    

---

상한과 최악

빅오는 최악, 평균, 최선 경우의 수행시간의 상한(Upper Bound)를 나타냅니다.

이 외에도 빅오메가(하한 - Lower Bound), 빅세타(평균)이 있지만 알고리즘의 표기는 상한을 사용합니다. 

---

분할 상환 분석

최악의 경우만을 살펴보는 것이 지나치게 비관적이라는 이유로 분할 상환 분석 방법이 등장하게 되었습니다. 

분할 상환 분석은 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산합니다. 

널리 보편적으로 사용되는 방법입니다. (평균과 비슷)

---

병렬화

병렬화는 동시에 수많은 계산을 하는 연산의 한 방법입니다. 

알고리즘을 병렬화하면 실행 속도를 높일 수 있습니다. 

GPU는 병렬 연산을 위한 대표적인 장치이기도 합니다.

* CPU보다 수백 배 더 많은 연산을 동시에 수행할 수 있습니다.