Big O 표기법

Big O 표기법의 주요 개념

1. 시간 복잡도(Time Complexity):
   • 알고리즘이 주어진 입력 크기(n)에 대해 얼마나 많은 시간을 소요하는지를 나타냅니다.
   • 예를 들어, 입력 크기가 10일 때와 1,000일 때의 알고리즘의 실행 시간이 어떻게 변하는지를 분석합니다.
2. 공간 복잡도(Space Complexity):
   • 알고리즘이 실행되는 동안 얼마나 많은 메모리를 사용하는지를 나타냅니다.
   • 입력 크기가 커질 때, 메모리 사용량이 어떻게 변하는지를 분석합니다.

 

Big O 표기법의 의미

Big O 표기법은 알고리즘의 성능을 상한으로 나타냅니다. 즉 해당 알고리즘이 얼마나 오랜시간에 걸려서 동작되는지 확인시키는데 사용됩니다.

 

---

Big O의 표기들

1. O(1) - 상수 시간(Constant Time):
   • 입력 크기에 상관없이 항상 동일한 시간이 걸리는 알고리즘.
   • 예: 배열에서 인덱스를 이용한 접근.
2. O(log n) - 로그 시간(Logarithmic Time):
   • 입력 크기가 증가할 때, 실행 시간이 로그(logarithm)에 비례하여 증가하는 알고리즘.
   • 예: 이진 탐색(Binary Search).
3. O(n) - 선형 시간(Linear Time):
   • 입력 크기에 비례하여 실행 시간이 증가하는 알고리즘.
   • 예: 배열의 모든 요소를 순회하는 연산.
4. O(n log n):
   • 입력 크기에 로그를 곱한 시간에 비례하여 실행 시간이 증가하는 알고리즘.
   • 예: 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort).
5. O(n²) - 이차 시간(Quadratic Time):
   • 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘.
   • 예: 이중 루프를 사용하는 버블 정렬(Bubble Sort).
6. O(2^n) - 지수 시간(Exponential Time):
   • 입력 크기가 증가할 때, 실행 시간이 지수적으로 증가하는 알고리즘.
   • 예: 피보나치 수열을 재귀적으로 계산하는 알고리즘(재귀적 접근).
7. O(n!) - 팩토리얼 시간(Factorial Time):
   • 입력 크기가 증가할 때, 실행 시간이 팩토리얼에 비례하여 증가하는 알고리즘.
   • 예: 순열을 계산하는 알고리즘.