Big O 표기법(Big O Notation)은 알고리즘의 시간 복잡도와 공간 복잡도를 분석하는 데 사용되는 수학적 표기법.
알고리즘이 입력 크기에 따라 얼마나 빠르게 실행되는지 또는 얼마나 많은 메모리를 사용하는지를 설명하는 데 유용.


시간 복잡도와 공간 복잡도

  • 시간 복잡도: 알고리즘이 실행되는 데 걸리는 시간을 입력의 크기와 관련하여 표.
    예를 들어, 입력이 증가함에 따라 실행 시간이 어떻게 변화하는지를 측정.

  • 공간 복잡도: 알고리즘이 사용하는 메모리의 양을 입력의 크기와 관련하여 표현.


Big O 표기법의 정의

Big O 표기법은 최악의 경우를 기준으로 알고리즘의 성능을 설명.

  • O(1): 상수 시간 복잡도. 입력 크기에 관계없이 일정한 시간 내에 실행.
  • O(log n): 로그 시간 복잡도. 입력 크기가 증가할 때 실행 시간이 로그에 비례하여 증가.
    이진 탐색 알고리즘이 대표적.
  • O(n): 선형 시간 복잡도. 입력 크기 n에 비례하여 실행 시간이 증가.
    예를 들어, 배열의 모든 요소를 순회하는 경우.
  • O(n log n): 로그 선형 시간 복잡도.
    일반적으로 효율적인 정렬 알고리즘(예: 병합 정렬, 퀵 정렬 등)의 시간 복잡도.
  • O(n²): 이차 시간 복잡도. 입력 크기 n에 대해 실행 시간이 n의 제곱에 비례.
    중첩된 반복문에서 발생할 수 있음.
  • O(2^n): 지수 시간 복잡도. 입력 크기 n에 대해 실행 시간이 2의 n 제곱에 비례.
    재귀적 알고리즘에서 자주 발생.
  • O(n!): 팩토리얼 시간 복잡도. 입력 크기가 n일 때, n!에 비례하여 실행.
    예를 들어, 모든 순열을 생성하는 알고리즘이 해당.


Big O 표기법의 중요성

  • 효율성 평가: 알고리즘의 성능을 정량적으로 평가할 수 있어, 다양한 알고리즘 간의 비교가 용이.
  • 최적화: 알고리즘을 개선하거나 최적화할 때, 어떤 부분에서 성능이 저하되는지를 이해하는 데 도움을 줌.
  • 입력 크기 증가에 대한 예측: 알고리즘이 처리해야 할 데이터의 양이 증가할 때, 성능의 변화 양상을 예측할 수 있음.

참고