# 공간 복잡도Space complexity

• 시간 복잡도가 확장성scalability을 예측하지만, 유일한 측정은 아니다.
• Space complexity: 알고리즘이 동작하면서 필요한 리소스에 대한 척도
• 컴퓨터에서 알고리즘을 위한 리소스는 메모리memory이다.

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

• sorted: array를 복사하고 출력하기 위해서 생성
• 공간 복잡도를 계산하기 위해서는 함수를 위해 할당된 메모리를 분석
• array.sorted()는 array와 같은 크기의 배열을 생성하기 때문에
  → 함수의 공간 복잡도는 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, currentValue만 할당한다.
• 따라서 공간 복잡도는 O(1)
  
  

🔖 출처

• Raywenderlich - Data structures algorithms in swift v4.0