[Data Structures & Algorithms in Swift ] Complexity

elbin·2023년 3월 24일

목록 보기

1/5

🥑 Time complexity

🍞 Constant time

상수 시간 알고리즘은 입력 크기에 관계없이 실행 시간이 동일한 알고리즘입니다.

func checkFirst(names: [String]) {
  if let first = names.first {
    print(first)
  } else {
    print("no names")
  }
}

names 배열의 크기는 이 함수의 실행 시간에 영향을 주지 않습니다.

입력에 10개의 항목이 있는지, 1000만 개의 항목이 있는지 여부에 관계없이 이 함수는 배열의 첫 번째 요소만 확인합니다. 다음은 시간 대 데이터 크기 사이의 그림에서 이 시간 복잡도를 시각화한 것입니다:

입력 데이터가 증가해도 알고리즘에 걸리는 시간은 변경되지 않습니다.
간략화를 위해 프로그래머는 다양한 크기의 시간 복잡성을 나타내기 위해 Big O 표기법으로 알려진 표기법을 사용합니다. 상수 시간에 대한 Big O 표기법은 O(1)입니다.

🍞 Linear time

func printNames(names: [String]) {
  for name in names {
    print(name)
  }
}

printNames 함수는 String 타입 배열의 모든 요소를 출력합니다.
입력 배열의 크기가 커지면 for 루프의 반복 횟수도 같은 양만큼 증가합니다.
이 동작을 선형 시간 복잡도라고 합니다.

선형 시간 복잡성은 일반적으로 가장 이해하기 쉽습니다.
데이터 양이 증가하면 실행 시간도 같은 양만큼 증가합니다.
선형 시간에 대한 Big O 표기법은 O(n)입니다.

🍞 Quadratic time

일반적으로 n 제곱이라고 하는 이 시간 복잡도는 입력 크기의 제곱에 비례하는 시간을 갖는 알고리즘을 나타냅니다.

func printNames(names: [String]) {
  for _ in names {
    for name in names {
      print(name)
    }
  }
}

이번에는 함수가 배열에 있는 모든 이름 배열에 대한 이름을 출력합니다. 만약 10개의 데이터가 있는 배열이라면 10개의 이름이 있는 전체목록을 10번씩 출력할 것입니다. 100개의 출력문이 되는 것입니다.

만약 인풋 사이즈가 하나 증가하면, 11개의 이름을 11번 출력하고, 121개의 출력문이 나오게 됩니다. 선형시간 동안 수행되는 이전 함수와 다르게, n 제곱 알고리즘은 데이터 사이즈가 증가할 수록 더 빠르게 통제를 잃을 수 있습니다.

인풋 데이터의 사이즈가 증가할 수록, 알고리즘을 수행하는 시간은 급격하게 증가합니다.
때문에 n 제곱 알고리즘은 규모에 따라 잘 수행되지 않습니다.
Big O 표기법으로 2차시간은 O(n²) 입니다.

선형 시간 O(n) 알고리즘이 아무리 비효율적으로 쓰였더라도, (다중 패스 등) 충분히 큰 n에 대해서 선형 알고리즘은 최적화된 2차시간 알고리즘보다 빠릅니다.

🍞 Logarithmic time

인풋의 서브셋만 검사하는 시나리오도 있습니다.

이러한 카테고리에 속하는 시간복잡도 알고리즘은 입력 데이터에 대해 몇가지 가정을 함으로써 몇가지 지름길을 활용할 수 있는 알고리즘입니다. 예를 들어 정렬된 정수 배열이 있다면, 특정값이 있는지 확인하는 가장 빠른 방법은 무엇일가요?

가장 단순한 솔루션은 결론에 도달하기 전까지 처음부터 끝까지 배열의 모든 요소를 검사하는 것입니다. 모든 요소를 한 번씩 검사한다면 O(n) 알고리즘이 될 것입니다. 선형시간 알고리즘도 물론 좋지만 더 잘할 수 있습니다. 인풋 배열이 정렬되어 있다면, 최적화할 수 있는 방법이 있습니다.

let numbers = [1, 3, 56, 66, 68, 80, 99, 105, 450]

func naiveContains(_ value: Int, in array: [Int]) -> Bool {
  for element in array {
    if element == value {
      return true
    }
  }

  return false
}

숫자 451이 있는지 찾기 위해서는, 단순한 알고리즘에서는 처음부터 끝까지 반복하는 것입니다. 9개의 값이 있는 배열에서는 9번의 검사가 이루어질 것입니다.

하지만 배열이 정렬되어 있다면 중간값을 검사해서 필요에 따라 값의 절반을 삭제할 수 있습니다.

func naiveContains(_ value: Int, in array: [Int]) -> Bool {
  guard !array.isEmpty else { return false }
  let middleIndex = array.count / 2

  if value <= array[middleIndex] {
    for index in 0...middleIndex {
      if array[index] == value {
        return true
      }
    }
  } else {
    for index in middleIndex..<array.count {
      if array[index] == value {
        return true
      }
    }
  }

  return false
}

위 함수는 결론까지 가기 위해 배열의 절반만을 검사하는 작지만 의미있는 최적화를 거쳤습니다.

이 알고리즘은 맨 처음으로 원하는 값과 배열의 중간값을 체크합니다. 만약 중간값이 원하는 값보다 크다면 알고리즘은 배열의 오른쪽 값을 살펴보지 않습니다. 배열이 정렬되어 있기 때문에 중간 값의 오른쪽 값들은 커질 뿐입니다.

반면에, 중간 값이 찾는 값보다 작다면 알고리즘은 배열의 왼쪽 값을 확인하지 않습니다. 이는 비교횟수를 절반으로 줄이는, 작지만 의미있는 최적화입니다.

필요한 비교를 반복적으로, 절반으로 낮추는 알고리즘은 로그 시간 복잡도를 가집니다. 아래 그래프는 인풋 데이터가 증가할수록 로그 시간 알고리즘이 어떻게 수행되는지 보여줍니다.

인풋 데이터가 증가해도 알고리즘을 실행하는 시간은 적은 비율로 증가합니다. 자세히 보면 위 그래프는 점근적인 모양새를 나타내고 있습니다.

수행해야되는 비교횟수를 절반으로 줄이는 것의 영향을 고려하여 설명할 수 있습니다.

인풋 사이즈가 100일 경우, 비교횟수를 50번 아낄 수 있습니다.
만약 인풋 사이즈가 10만일 경우 비교횟수로 5만을 아낄 수 있습니다.
더 많은 데이터가 있을수록, 반감효과도 커집니다. 때문에 위 그래프가 수평에 가까워지는 것을 볼 수 있습니다.

이런 종류의 알고리즘은 매우 없지만, 사용되는 경우 매우 강력합니다. 로그시간 알고리즘의 Big O 표기법은 O(log n) 입니다.

🍞 Quasilinear time

유사선형 시간 알고리즘은 선형시간보다 성능이 나쁩니다.
하지만 평방 시간보다는 극적으로 좋습니다.
유사 선형시간의 한 예로는 Swift의 sort 메서드가 있습니다.

유사선형시간의 Big O 표기법은 O(n log n) 입니다.
선형시간과 로그시간 알고리즘을 곱한 형태입니다. 때문에 유사 선형시간은 로그 시간과 선형시간 사이에 딱 맞습니다.
선형시간보다 성능이 나쁘지만 앞으로 보게 될 많은 다른 복잡도보다는 낫습니다.

유사선형시간(Quasilinear time) 복잡도는 평방 시간 복잡도와 유사한 형태의 곡선을 공유합니다. 하지만 그렇게 빠르게 올라가지 않으므로 대규모의 데이터를 다루는 데 더욱 탄력적입니다.

🍞 Other time complexities

시간 복잡도가 성능에 대한 높은 수준의 대요이며, 일반적인 순위체계를 넘는 알고리즘을 속도로 판단하지 않습니다.
이 말은, 두 알고리즘이 동일한 시간복잡도를 가지더라도 하나가 다른 하나보다 월등히 빠를 수 있다는 것입니다.
또한, 작은 데이터 세트에서 시간 복잡도는 실제 속도를 측정하는 데 정확하지 않을 수 있습니다.

예를 들어, 삽입 정렬과 같은 평방시간 알고리즘은 병합정렬과 같은 유사선형 알고리즘보다 빠를 수 있습니다. 그 이유는 삽입 정렬은 알고리즘을 수행하는데 추가적인 메모리 할당이 필요하지 않기 때문입니다.

반면, 병합 정렬은 여러 배열을 할당해야 합니다. 작은 데이터세트에서 메모리 할당은 알고리즘이 건드리는 요소의 수와 관련하여 비싸질 수 있습니다.

🍞 Comparing time complexity

1부터 n까지 합을 찾는 아래와 같은 코드를 작성한다고 가정하면

func sumFromOne(upto n: Int) -> Int {
  var result = 0
  for i in 1...n {
    result += i
  }
  return result
}

sumFromOne(upto: 10000)

위 코드는 1만번 반복하고 값 50005000을 반환할 것이고 O(n)입니다.
반복문과 출력결과를 나타내므로 playground에서 실행하는 데 시간이 좀 걸릴 것입니다.

또 다른 예시로

func sumFromOne(upto n: Int) -> Int {
  (1...n).reduce(0, +)
}
sumFromOne(upto: 10000)

이 코드는 playground에서 더 빨리 돌아갈 것입니다.
왜냐하면 이 코드는 표준 라이브러리에서 컴파일된 코드를 불러오기 때문입니다.

하지만 만약 시간복잡도를 줄이고자 한다면, 위 코드 역시 + 메소드를 n번 호출한다는 점에서 O(n) 임을 알게될 것입니다. 두 코드 Big O 표기법이 동일하지만 위 코드는 이미 컴파일된 코드이기 때문에, 더 작은 상수를 가지고 있습니다.

최종적으로 아래와 같이 작성할 수 있습니다.

func sumFromOne(upto n: Int) -> Int {
  (n + 1) * n / 2
}
sumFromOne(upto: 10000)

이 버전의 함수는 프레드릭 가우스(Fredrick Gauss)가 초등학교때 알아차린 트릭을 사용합니다. 즉 여러분은 단순한 산술로 이 모든 덧셈을 계산할 수 있게 됩니다.
이 버전의 알고리즘은 O(1) 으로 어떤 알고리즘도 이길 수 없습니다. 상수시간 알고리즘은 언제나 가장 선호됩니다.
이 버전을 반복문 안에 넣을 경우, 선형시간(Linear time)으로 끝나지만 이전의 O(n) 버전은 느린 평방시간의 하나의 외부 반복문(just one outer loop away)이 될 것입니다.

🥑 Space complexity

알고리즘의 시간복잡도는 확장성을 예측하는데 도움이 되지만, 유일한 지표는 아닙니다. 공간복잡도는 알고리즘이 실행되는 데 필요한 자원을 측정하는 방법으로, 컴퓨터 상에서 알고리즘을 위한 자원은 바로 메모리가 됩니다.

func printSorted(_ array: [Int]) {
  let sorted = array.sorted()
  for element in sorted {
    print(element)
  }
}

위 함수는 정렬된 복사본을 만들어 출력하는 함수입니다.

공간 복잡도를 계산하기 위해서는 해당 함수의 메모리 할당을 분석하게 됩니다.

array.sorted() 메서드가 array 와 동일한 사이즈의 새 배열을 만드므로, printSorted 의 공간복잡도는 O(n)이 됩니다. 이 함수도 물론 간단하고 우아하지만, 메모리를 가능한 적게 할당하고 싶은 상황이 생길수도 있습니다. 이 때 위 함수를 아래처럼 수정할 수 있을 것입니다.

func printSorted(_ array: [Int]) {
  // 1
  guard !array.isEmpty else { return }

  // 2
  var currentCount = 0
  var minValue = Int.min

  // 3
  for value in array {
    if value == minValue {
      print(value)
      currentCount += 1
    }
  }

  while currentCount < array.count {

    // 4
    var currentValue = array.max()!

    for value in array {
      if value < currentValue && value > minValue {
        currentValue = value
      }
    }

    // 5
    for value in array {
      if value == currentValue {
        print(value)
        currentCount += 1
      }
    }

    // 6
    minValue = currentValue
  }
}

위에서 구현한 코드는 공간제약을 염두하였습니다. 목표는 배열을 여러번 반복하고, 각 반복에서 가장 작은 값을 출력하는 것입니다.

만약 배열이 비었을 경우를 체크합니다. 비었다면 아무것도 출력하지 않습니다.
currentCount 는 출력문의 숫자를 추적하고, minValue 는 마지막으로 출력한 값을 저장합니다.
알고리즘은 minValue 에 일치하는 모든 값을 출력하고, 출력문의 숫자에 따라 currentCount 의 값을 업데이트합니다.
while 반복문에서, 알고리즘은 minValue 보다는 큰, 가장 작은 값을 찾고, 이를 currentValue 에 저장합니다.
currentCount를 업데이트 하면서 배열 내부의 모든 currentValue 값을 출력합니다.
minValue 가 currentValue 로 세팅되면 다음 반복에서는 그 다음 최소값을 찾습니다.

위 알고리즘은 적은 수의 변수를 추적하기 위한 메모리만 할당합니다. 때문에 공간복잡도는 O(1)이 됩니다. 소스배열의 정렬된 형태를 만들기 위해 배열 전체를 할당하는 이전 함수와 대조적이 됩니다.

🥑 Other notations

이제까지 Big O 표기법을 사용하여 알고리즘을 측정하였습니다. 현재까지 프로그래머들이 측정할 때 사용하는 가장 일반적인 측정법입니다. 하지만 이외에도 다른 표기법이 존재합니다.

Big Omega 표기법은 알고리즘의 최상의 실행시간을 측정하는데 사용합니다. 최상의 케이스를 찾는 것이 때로 쉽지 않기 때문에 Big O 표기법만큼 유용하지는 않습니다.

Big Theta 표기법은 최상의 경우와 최악의 경우가 같을 경우 런타임을 측정하는데 사용됩니다.

👀 Key points

시간복잡도는 인풋 사이즈가 증가할수록, 알고리즘을 실행하는데 필요한 시간을 측정하는 기법입니다.
상수시간, 로그시간, 선형시간, 유사선형시간, 평방시간을 알고 이를 비용순으로 정렬할 수 있어야합니다.
공간복잡도는 알고리즘을 수행하는데 필요한 자원을 측정하는 기법입니다.
Big O 표기법은 시간복잡도와 공간복잡도를 표현하는 일반적인 형태입니다.
시간과 공간 복잡도는 확장성을 상위레벨로 측정한 것입니다. 실제 알고리즘 자체를 측정하지 않습니다.
작은 데이터세트에서 시간 복잡도는 보통 관련이 없습니다. 예를 들어 유사선형 알고리즘은 n이 작을 경우 평방시간보다 작을 수 있습니다.

해당 포스팅은 RaywenderLich의 ePub을 학습 후 정리한 포스팅입니다.

Elbin

쑥쑥 자라고 싶은 iOS 꿈나무 🌱

다음 포스트

[Data Structures & Algorithms in Swift ] Complexity