빅-오 표기법 Big-O Notation

빅-오 표기법

알고리즘이 얼마나 빠른지를 아는 것과 그 알고리즘이 얼만큼의 공간을 사용해야하는지를 아는 것은 유용합니다. 또한, 이 표기법은 올바른 알고리즘을 선택하는 것에 도움을 줍니다.

빅-오 표기법은 알고리즘이 진행하는 시간에 대한 대략적인 지표를 알려줍니다. 알고리즘의 메모리 사용량 또한 그렇습니다. 누군가 다음과 같이 말한다면, “이 알고리즘은 최악의 경우 O(n^2)이며 O(n) 공간을 사용한다.” 이 말의 의미는 조금 느리지만 추가적인 메모리가 많이 필요하진 않다는 것입니다.
알고리즘의 빅오를 파악하는 것은 수학적인 분석법을 통해 이루어집니다. 여기서는 수학을 이용하는 것을 피하겠지만 다른 값들이 무엇을 의미하는지 아는 것은 중요합니다. n은 여러분이 처리해야할 데이터 아이템의 개수를 말합니다. 예를 들어 100개의 아이템을 가진 배열을 정렬하려면 n=100입니다.

빅-오	Name	Description
O(1)	상수(constant)	이 방법은 최고의 성능을 가집니다. 이 알고리즘은 얼만큼의 데이터를 처리하는지와 상관없이 항상 똑같은 시간에 처리됩니다. 예제: 배열의 원소를 인덱스로 접근하여 탐색
O(log n)	logarithmic	매우 좋은 성능을 가집니다. 이 종류의 알고리즘은 한 번 반복할 때마다 데이터의 양을 둘로 나눕니다. 만약 100개의 아이템을 가지고 있다면 답을 찾는 데에는 7번의 반복이 필요합니다. 1,000개의 아이템을 가진다면 10번의 반복이 필요합니다. 1,000,000개의 아이템이라면 오로지 20번의 반복을 수행하면 됩니다. 매우 큰 양의 데이터에도 매우 빠른 속도를 가집니다. 예제: 이진 탐색
O(n)	선형(linear)	좋은 성능을 가집니다. 만약 100개의 아이템을 가진다면, 100개의 작업을 수행하면 됩니다. 아이템의 갯수를 2배로하면 정확히 2배의 시간이 소요됩니다. 예제: 순차 탐색
O(n log n)	"linearithmic"	적절한 성능을 가집니다. 이 방법은 선형보다는 다소 좋지 않는 성능을 가집니다. 예제: 가장 빠른 정렬 알고리즘
O(n^2)	quadratic	조금 느립니다. 여러분이 만약 100개의 아이템을 가지고 있다면, 이것은 100^2 = 10,000 번의 작업을 수행해야 합니다. 아이템의 갯수를 두 배로 해보면, 4배 느려집니다. 예제: 삽입 정렬과 같은 이중 반복문
O(n^3)	cubic	좋지 못한 성능을 가집니다. 만약 100개의 아이템을 가진다면 100^3 = 1,000,000 만큼의 작업이 필요합니다. 아이템을 두 배로 한다면 수행하는 작업의 수는 8배 늘어납니다. 예제: 행렬 곱
O(2^n)	exponential	매우 좋지 못한 성능을 가집니다. 만약 이러한 종류의 알고리즘을 피하고 싶지만 대안이 없을 수도 있습니다. 단지 입력 값에 한 개의 비트만 추가해도 2배의 시간이 소모됩니다. 예제: 세일즈맨의 순회 문제
O(n!)	factorial	참을 수 없을 정도로 느립니다.

아래의 예제를 통해 성능별로 분류를 하였습니다.

O(1)

​ 가장 일반적인 O(1) 복잡도의 예제는 배열의 번호를 통해 배열에 접근하는 것입니다.

  let value = array[5]

O(1)의 다른 예제로는 스택에서 값을 빼거나 넣는 것이 있습니다.

O(log n)

  var j = 1
  while j < n {
    // do constant time stuff
    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
      // do constant time stuff
    }
  }

OR

  for i in stride(from: 0, to: n, by: 1) {
    func index(after i: Int) -> Int? { // `i` 가 `n`보다 크거나 같아질 때 까지 `i`를 곱합니다.
      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) {
        // do constant time stuff
      }
    }
  }

O(2^n)

​ O(2^N) 시간 만큼이 소모되는 알고리즘은 보통 재귀 알고리즘입니다. 재귀 알고리즘은 크기가 N인 값을 재귀적으로 N-1인 값으로 해결합니다. 아래의 예제는 "하노이의 탑"입니다.

  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!)

  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)으로 그 보다 더 낫습니다. 하지만 적은 양의 데이터로는 삽입 정렬이 배열이 부분적으로 정렬되어 있을 경우에 더 빠릅니다.

만약 이러한 것들이 이해가 되지 않는다면 빅-오를 크게 신경쓰지 마세요. 이것은 대부분 두 개의 알고리즘 중 어느것이 더 나은지에 대해 비교를 할 때 유용합니다. 이후에는 어느 것이 더 최선인지를 테스트할 때 사용하기 원할 것입니다. 만약 데이터의 양이 상대적으로 적다면 매우 느린 알고리즘이라도 충분히 빠를 수 있습니다.