빅 오(Big O).md

빅 오(Big O) 표기법

빅 오(Big O) 표기법은 알고리즘의 시간 복잡도나 공간 복잡도를 표현할 때 사용하는 수학적 표기 방법입니다. 이 표기법은 알고리즘이 어떤 크기의 입력에 대해 얼마나 많은 연산을 수행하거나 얼마나 많은 메모리를 사용하는지를 나타내는 데 사용됩니다. 빅 오 표기법은 최악의 경우의 성능을 기준으로 하며, 입력 크기가 커질 때 알고리즘의 실행 시간이나 필요한 공간이 어떻게 증가하는지를 설명합니다.

• 시간 복잡도: 알고리즘이 얼마나 빠르게 실행될 수 있는지를 나타냅니다. 시간 복잡도가 높은 알고리즘은 큰 입력에 대해 매우 느려질 수 있으므로, 효율적인 알고리즘을 선택하는 데 중요한 기준이 됩니다.
• 공간 복잡도: 알고리즘이 얼마나 많은 메모리를 사용하는지를 나타냅니다. 메모리 사용이 많은 알고리즘은 제한된 메모리 자원을 가진 시스템에서 문제를 일으킬 수 있습니다.

빅 오 표기법의 기본적인 예시는 다음과 같습니다:

1. O(1): 상수 시간(Constant time) - 입력 크기에 상관없이 알고리즘의 실행 시간이 일정합니다.
2. O(log n): 로그 시간(Logarithmic time) - 알고리즘의 실행 시간이 입력 크기의 로그에 비례하여 증가합니다. 이진 탐색이 대표적인 예입니다.
3. O(n): 선형 시간(Linear time) - 알고리즘의 실행 시간이 입력 크기에 비례하여 증가합니다. 예를 들어, 배열을 한 번 순회하는 경우입니다.
4. O(n log n): 선형 로그 시간(Linearithmic time) - 많은 효율적인 정렬 알고리즘들이 이 시간 복잡도를 가집니다.
5. O(n^2): 제곱 시간(Quadratic time) - 알고리즘의 실행 시간이 입력 크기의 제곱에 비례하여 증가합니다. 간단한 이중 루프를 사용하는 알고리즘들이 이에 해당합니다.
6. O(2^n): 지수 시간(Exponential time) - 알고리즘의 실행 시간이 입력 크기에 대한 2의 거듭제곱에 비례하여 증가합니다. 일부 분할 정복 알고리즘과 조합 문제를 해결할 때 나타날 수 있습니다.
7. O(n!): 팩토리얼 시간(Factorial time) - 알고리즘의 실행 시간이 입력 크기의 팩토리얼에 비례하여 증가합니다. 가장 느린 성능을 보이며, 일부 순열 문제를 해결할 때 나타날 수 있습니다.

빅 오 표기법은 최악의 경우를 기준으로 하기 때문에, 알고리즘의 평균적인 성능이나 최선의 성능을 설명하지는 않습니다. 그러나 알고리즘을 비교하고 분석할 때 유용한 도구로 사용됩니다.

Reference

• www.google.com

---

Back