빅오 표기법에 대한 설명

알고리즘의 속도와 메모리 사용량을 아는 것은 중요하다. 이를 통해 적절한 알고리즘을 선택할 수 있다.

빅오 표기법은 알고리즘의 실행 시간과 메모리 사용량을 대략적으로 나타낸다. 누군가 "이 알고리즘의 최악의 경우 실행 시간은 **O(n^2)**이고, 메모리 사용량은 **O(n)**이다"라고 말한다면, 이 알고리즘이 다소 느리지만 추가 메모리를 많이 필요로 하지 않는다는 의미다.

알고리즘의 빅오를 계산하는 것은 일반적으로 수학적 분석을 통해 이루어진다. 여기서는 수학적 내용을 생략하지만, 각 값이 무엇을 의미하는지 아는 것이 유용하다. 다음은 주요 빅오 표기법을 정리한 표다. n은 처리하는 데이터의 개수를 의미한다. 예를 들어, 100개의 항목을 가진 배열을 정렬할 때 n = 100이다.

빅오	이름	설명
O(1)	상수 시간	가장 좋은 경우. 데이터 양과 상관없이 항상 동일한 시간이 소요된다. 예: 배열의 인덱스를 통해 요소에 접근하는 경우.
O(log n)	로그 시간	매우 빠름. 이 알고리즘은 각 반복마다 데이터 양을 절반으로 줄인다. 100개의 항목이 있다면 약 7단계를 거쳐 답을 찾는다. 1,000개의 항목은 10단계, 1,000,000개의 항목은 20단계가 소요된다. 대량의 데이터에서도 매우 빠르다. 예: 이진 탐색.
O(n)	선형 시간	좋은 성능. 100개의 항목이 있다면 100단위의 작업을 수행한다. 항목 수가 두 배가 되면 알고리즘은 정확히 두 배의 시간이 소요된다(200단위의 작업). 예: 순차 탐색.
O(n log n)	선형 로그 시간	괜찮은 성능. 선형 시간보다 약간 느리지만 크게 나쁘지 않다. 예: 가장 빠른 범용 정렬 알고리즘.
O(n^2)	제곱 시간	다소 느림. 100개의 항목이 있다면 100^2 = 10,000단위의 작업을 수행한다. 항목 수가 두 배가 되면 네 배 느려진다(2의 제곱은 4이기 때문). 예: 삽입 정렬과 같은 중첩 루프를 사용하는 알고리즘.
O(n^3)	세제곱 시간	낮은 성능. 100개의 항목이 있다면 100^3 = 1,000,000단위의 작업을 수행한다. 입력 크기가 두 배가 되면 여덟 배 느려진다. 예: 행렬 곱셈.
O(2^n)	지수 시간	매우 낮은 성능. 이런 알고리즘은 피하는 것이 좋지만, 때로는 선택의 여지가 없다. 입력에 단 하나의 비트를 추가해도 실행 시간이 두 배가 된다. 예: 외판원 문제.
O(n!)	팩토리얼 시간	극도로 느림. 말 그대로 백만 년이 걸린다.

다음은 각 성능 범주에 대한 예제다:

O(1)

O(1) 복잡도의 가장 일반적인 예는 배열 인덱스에 접근하는 것이다.

let value = array[5]

스택에서 푸시와 팝을 수행하는 것도 O(1)의 예이다.

O(log n)

var j = 1
while j < n {
  // 상수 시간 작업 수행
  j *= 2
}

단순히 증가시키는 대신, 'j'는 각 실행마다 2배씩 증가한다.

이진 탐색 알고리즘이 O(log n) 복잡도의 예이다.

O(n)

for i in stride(from: 0, to: n, by: 1) {
  print(array[i])
}

배열 순회와 선형 탐색이 O(n) 복잡도의 예이다.

O(n log n)

for i in stride(from: 0, to: n, by: 1) {
  var j = 1
  while j < n {
    j *= 2
    // 상수 시간 작업 수행
  }
}

또는

for i in stride(from: 0, to: n, by: 1) {
  func index(after i: Int) -> Int? { // `i`가 `n`보다 작을 때까지 `i`를 2배씩 증가
    return i < n ? i * 2 : nil
  }
  for j in sequence(first: 1, next: index(after:)) {
    // 상수 시간 작업 수행
  }
}

병합 정렬과 힙 정렬이 O(n log n) 복잡도의 예이다.

O(n^2)

for i in stride(from: 0, to: n, by: 1) {
  for j in stride(from: 1, to: n, by: 1) {
    // 상수 시간 작업 수행
  }
}

간단한 2차원 배열 순회와 버블 정렬이 O(n^2) 복잡도의 예이다.

O(n^3)

for i in stride(from: 0, to: n, by: 1) {
  for j in stride(from: 1, to: n, by: 1) {
    for k in stride(from: 1, to: n, by: 1) {
      // 상수 시간 작업 수행
    }
  }
}

O(2^n)

O(2^N) 실행 시간을 가진 알고리즘은 일반적으로 크기 N의 문제를 크기 N-1의 두 개의 작은 문제로 재귀적으로 해결한다.
다음 예제는 N개의 디스크로 이루어진 유명한 "하노이의 탑" 문제를 해결하기 위한 모든 이동을 출력한다.

func solveHanoi(n: Int, from: String, to: String, spare: String) {
  guard n >= 1 else { return }
  if n > 1 {
      solveHanoi(n: n - 1, from: from, to: spare, spare: to)
      solveHanoi(n: n - 1, from: spare, to: to, spare: from)
  }
}

O(n!)

O(n!) 시간이 소요되는 함수의 가장 간단한 예는 다음과 같다.

func nFactFunc(n: Int) {
  for i in stride(from: 0, to: n, by: 1) {
    nFactFunc(n: n - 1)
  }
}

종종 수학적 계산 없이도 알고리즘의 빅오를 직관적으로 파악할 수 있다. 코드가 모든 n개의 입력 요소를 살펴보는 단일 루프를 사용한다면, 그 알고리즘은 **O(n)**이다. 두 개의 중첩 루프를 사용한다면 **O(n^2)**이다. 세 개의 중첩 루프는 **O(n^3)**을 의미한다.

빅오 표기법은 추정치이며, 주로 큰 n 값에 유용하다. 예를 들어, 삽입 정렬 알고리즘의 최악의 경우 실행 시간은 **O(n^2)**이다. 이론적으로는 병합 정렬의 실행 시간인 **O(n log n)**보다 나쁘다. 하지만 작은 양의 데이터에서는 삽입 정렬이 실제로 더 빠르며, 특히 배열이 부분적으로 정렬된 상태라면 더욱 그렇다.

이 내용이 혼란스럽다면 너무 걱정하지 않아도 된다. 빅오 표기법은 주로 두 알고리즘을 비교해 어떤 것이 더 나은지 판단할 때 유용하다. 하지만 결국 실제로 테스트해보는 것이 가장 좋다. 데이터 양이 상대적으로 작다면, 느린 알고리즘도 실용적으로 충분히 빠를 수 있다.