[빅오]

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

(1)O(1): 입력값이 아무리 커도 실행 시간은 일정하다. 최고의 알고리즘이라고 할 수 있다. 해쉬 테이블 조회 및 삽입이 이에 해당한다.

(2)O(log n): 여기서 부터 실행 시간은 입력값에 영향을 받는다. 그러나 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 웬만한 n의 크기에 대해서 매우 견고하다. 대표적으로 이진 검색이 이에 해당한다.

(3)O(n): 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는데 걸리는 시간은 입력값에 비례한다. 선형시간 알고리즘이라고 불린다. 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우가 이에 해당하며, 이 값을 찾기 위해서 모든 입력 값을 적어도 한 번 이상은 살펴 봐야한다.

(4)O(nlogn): 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(nlogn)보다 빠를 수 없다. 물론 입력 값이 최선인 경우, 비교를 건너 뛰어 O(n)이 될 수 있으며, 팀소트가 이런 로직을 가지고 있다.

(5)O(n^2): 버블 정렬과 같은 비효율적인 정렬 알고리즘이 이에 해당한다.

(6)O(2^n): 피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다. 간혹 n^2과 2^n을 헷갈릴 수 있는데, 2^n이 훨씬 크다.

(7)O(n!): 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때가 이에 해당한다.

평균: 빅세타

가장 빨리 실행됨: 빅오메가

빅오 표기법은 무조건 최악의 실행을 말하는게 아니다. 최선/최악/평균 경우의 수행 시간의 상한을 나타낸다.

[분할 상환 분석]

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

[병렬화]

GPU를 통한 알고리즘 병렬화 실행으로 실행 속도를 높일 수 있다.