빅오(big-O)

2023.02.23

1. 빅오

✔ 빅오 - 점근적 실행 시간을 표기할 때 가장 널리 쓰이는 수학적 표기법
✔ 점근적 실행 시간(시간 복잡도) - 입력값이 무한대를 향할 때 함수의 실행 시간의 추이
✔ 시간 복잡도 - 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미
✔ 빅오로 시간 복잡도를 표현할때는 최고차항만 표기하고 계수는 무시
✔ 빅오 표기법의 종류

1. O(1) - 입력값이 아무리 커도 실행 시간은 일정
   (해시 테이블의 조회 및 삽입)
2. O(logn) - 실행 시간은 입력값에 영향을 받음 다만 웬만한 n의 크기에 대해서도 견고
   (이전 검색)
3. O(n) - 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례 = 선형 시간 알고리즘
   (정렬되지 않은 리스트에서의 최댓값 또는 최솟값 찾기 -> 적어도 한 번 이상 살핌)
4. O(nlogn) - 효율 좋은 정렬 알고리즘이 해당
   (병합 정렬, 비교 기반 정렬 알고리즘)
5. O(n^2) - 비효율적인 정렬 알고리즘
   (버블 정렬)
6. O(2^n) - 피보나치수를 재귀로 계산하는 알고리즘, n^2보다 훨씬 크다.
   (피보나치 수)
7. O(n!) - 가장 느린 알고리즘
   (각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이 할 떄)

2. 상한과 최악

✔ 빅오 - 상한(가장 늦게 실행될 때)을 의미
✔ 빅오메가 - 하한(가장 빨리 실행될 때)을 의미
✔ 빅세타 - 평균을 의미

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

3. 분할 상환 분석

✔ 분할 상환 분석은 빅오와 함께 함수의 동작을 설명할 때 중요한 분석 방법 중 하나
✔ 시간 또는 메모리를 분석하는 알고리즘의 복잡도를 계산할 때, 알고리즘 전체를 보지 않고 최악의 경우만을 살펴보는 것은 지나치게 비관적이라는 이유로 분할 상환 분석 방법이 등장하는 계기가 됨

4. 병렬화

✔ 일부 알고리즘들은 병렬화로 실행 속도를 높일 수 있음
✔ GPU는 병렬 연산을 위한 대표적인 장치
✔ 알고리즘 자체의 시간 복잡도 외에도 알고리즘이 병렬화가 가능한지는 근래에 알고리즘의 우수성을 평가하는 매우 중요한 척도 중 하나