### Big-O

빅오 표기법(Big-O notation)은 알고리즘의 성능, 특히 시간 복잡도와 공간 복잡도를 수학적으로 표현하기 위한 방법론이다. 이 표기법은 특정한 문제의 입력 크기가 무한히 커질 때, 알고리즘이 기초적으로 얼마나 많은 자원을 필요로 하는지를 나타낸다. 빅오는 알고리즘의 최악의 경우 성능을 설명하는 데 사용되며, 입력 크기에 따라 알고리즘의 성능을 비교하는 데 유용하다.

빅오 표기법은 다음과 같은 형식으로 표현된다: O(f(n)), 여기서 f(n)은 입력 크기 n에 대한 함수로, 알고리즘의 실행 시간이나 공간 사용량을 나타낸다. 이때, O 앞의 f(n)은 입력이 증가함에 따라 알고리즘의 성능이 어떻게 변화하는지를 나타내는 대략적인 경향을 보여준다.

일반적으로 사용되는 빅오 표기의 예로는 다음과 같은 것들이 있다:

- O(1): 입력 크기와 관계없이 일정한 시간 또는 공간을 필요로 하는 경우. 예를 들어, 배열의 첫 번째 요소에 접근하는 것이 이에 해당한다.

- O(log n): 입력 크기가 증가함에 따라 수행시간이 로그 함수에 비례해 증가하는 경우. 이진 탐색 알고리즘이 이 예에 포함된다.

- O(n): 입력 크기에 비례하여 수행시간이 증가하는 경우. 예를 들어, 배열의 모든 요소를 순회하는 경우가 이에 해당한다.

- O(n log n): 입력 크기와 로그 함수의 곱에 비례하여 수행시간이 증가하는 경우. 일반적으로 분할 정복 알고리즘에서 자주 나타난다.

- O(n^2): 입력 크기의 제곱에 비례하여 수행시간이 증가하는 경우. 이중 루프 구조를 가진 알고리즘에서 흔히 볼 수 있다.

- O(2^n): 입력 크기가 증가할수록 수행시간이 기하급수적으로 증가하는 경우. 재귀적으로 정의된 피보나치 수열 계산 알고리즘이 이 예에 해당한다.

빅오 표기법은 성장률을 기반으로 하기 때문에, 상수 계수나 낮은 차수의 항은 생략된다. 예를 들어, O(2n) 및 O(n) 모두 O(n)으로 간주된다. 이러한 이유로, 빅오 표기법은 알고리즘의 성능을 단순화하고 비교하기 위한 매우 강력한 도구로 자리 잡았다.

알고리즘 설계 및 분석에서 빅오 표기법은 중요한 역할을 하며, 선택된 알고리즘의 효율성을 이해하고 최적의 솔루션을 찾는 데 기여한다.