[알고리즘] Big O 표기법

복잡도 표기 방법 종류

• Big-O : 최악의 경우에 대비하여 나타냄
• Big-Ω : 최선의 경우에 대비하여 나타냄
• Big-θ : 중간(평균)의 경우에 대비하여 나타냄

Big O 표기법

• Big O 표기법

  • 알고리즘의 효율성을 설명하는 데 사용되는 수학적 표기법
  • 알고리즘이 어떤 입력 크기 n에 대해 얼마나 많은 연산을 필요로 하는지(시간복잡도)를 표현하는 데 많이 사용
  • 항상 최악의 경우를 대비하여 나타낸다.
  • 최선, 중간의 경우보다 "이 정도 시간까지 걸릴 수 있다"를 고려해야 그에 맞는 대응이 가능하다. 따라서 Big-O 표기법을 많이 사용한다.

• Big O 표기법 특징

  • 앞에 상수 등을 붙여서 나타내지 않고, 여러 항이 있다면 가장 오래 걸리는 것만을 나타낸다.
    • 앞의 상수와 뒤의 항들은 데이터가 매우 커졌을 때, 크게 의미가 떨어지므로 표기하지 않는다.
  • 예를 들어 $O(3nlogn + 5n)$의 경우, $O(nlogn)$으로 나타낸다.

Big O 표기법 종류

• $O(1)$ - 상수 시간 (Constant Time)
  • 입력 데이터의 크기와 상관없이 알고리즘의 실행 시간이 일정합니다. 알고리즘이 항상 일정한 단계의 연산을 수행하기 때문입니다.
• $O(log n)$ - 로그 시간 (Logarithmic Time)
  • 입력 데이터를 반으로 나눠가며 문제를 해결하는 알고리즘 (예: 이진 탐색)에서 나타납니다. 각 단계에서 입력 데이터의 크기가 절반으로 줄어들기 때문에 로그 시간복잡도를 가집니다.
• $O(n)$ - 선형 시간 (Linear Time)
  • 입력 데이터의 각 요소를 한 번씩만 처리하는 알고리즘에서 나타납니다. 예를 들어 배열의 모든 요소를 순회하는 경우에 해당됩니다.
• $O(n log n)$ - 선형 로그 시간
  • 대표적으로 효율적인 정렬 알고리즘 (예: 병합 정렬, 퀵 정렬)에서 볼 수 있습니다. 여기서 n은 데이터를 처리하는 것, log n은 데이터를 나누는 것을 의미합니다.
• *$O(n^2)$ - 제곱 시간 (Quadratic Time)
  • 두 개의 중첩 루프를 사용하여 데이터의 모든 쌍을 비교하는 알고리즘 (예: 버블 정렬, 삽입 정렬)에서 나타납니다.
• $O(2^n)$, $O(n!)$ 크기가 증가함에 따라 성능이 매우 안좋아지므로 사용하지 말자.

복잡도 (Complexity)

• 시간 복잡도 (Time Complexity)

  • 알고리즘이 어떤 문제를 해결하는데 얼마나 많은 시간이 걸리 는지를 나타내는 척도
  • 빅 오 표기법은 주로 시간복잡도를 나타낼 때 사용한다.
  • 예를 들어 특정 배열을 한번씩 순회하면서 작업해야 한다면, $O(n)$의 시간 복잡도를 가진다

• 공간 복잡도 (Space Complexity)

  • 알고리즘이 어떤 문제를 해결하는데 얼마나 많은 메모리 공간을 사용하는지를 나타내는 척도
  • 빅 오 표기법을 이용하여 나타낼 수 있다.
  • 예를 들어 특정 배열을 한번씩 순회하면서 각 원소를 메모리에 할당해야 한다면, $O(n)$의 공간 복잡도를 가진다