iOS Swift의 자료구조, 알고리즘에 대해서 알아보자 (2)

2024.10.28 - [◽️ Programming/◽️ Computer Science] - iOS Swift의 자료 구조, 알고리즘에 대해서 알아보자 (1)

iOS Swift의 자료 구조, 알고리즘에 대해서 알아보자 (1)

 

1편에 이어서 복잡도에 대해서 더 알아보자!!

 

• 로그 시간 Logarithmic time

앞서 1편에서 인풋의 모든 요소가 최소 한번씩 검사되는 선형복잡도와 2차 시간 복잡도에 대해 알아보았다. 그러나 이 방법도 있지만 인풋의 서브셋만 검사하는 시나리오도 있다.

 

이러한 카테고리에 속하는 시간복잡도 알고리즘은 입력 데이터에 대해 몇가지 가정하면서 몇가지 지름길을 활용할 수 있는 알고리즘이다.

 

예를 들어 정렬된 정수 배열이 있다면, 특정값이 있는지 확인하는 가장 빠른 방법은 무엇일까?

 

가장 단순한 솔루션은 결론에 도달하기 전까지 처음부터 끝까지 배열의 모든 요소를 검사하는 것이다. 모든 요소를 한번씩 검사하면 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이 있는지 찾기 위해서는 단순 알고리즘에서는 처음부터 끝까지 확인해 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
}

코드로 봤을땐 물론 배열이 적어 이 코드가 더 복잡해 보이고 비효율적이라고 생각할 수 있지만 코드를 살펴보고 다루는 데이터가 늘어난다

면 중간값을 확인하고 정답에 가까운 방향을 선택한다면 절반을 아예 확인하지 않아도 되면서 효율성을 2배를 챙길 수 있다는 것이다.

 

이 방법을 활용해 최적화를 반복적으로 수행하게되면 어떻게 되는지 다음 챕터에서 다루는 이진탐색 Binary Search에서 자세하게 알아보도록 하자.

 

이렇게 찾아야하는 데이터의 횟수를 반으로 낮추는 알고리즘은 아래 사진과 같이 로그 시간 복잡도를 가진다.

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

 

• 유사 선형 시간 Quasilinear time

또 다른 시간 복잡도는 유사선형 시간이다. 유사선형 시간 알고리즘은 선형 시간보다 성능이 좋지 않다. 하지만 평방 시간보다는 매우 좋다. 그리고 우리가 다루게 될 가장 일반적인 알고리즘 중 하나이다. 우리가 Swift에서 사용하는 한 예로는 sort 메서드가 있다.

 

유사선형시간의 Big O 표기법은 O(n log n)이다. 선형 시간과 로그시간 알고리즘을 곱한 형태로 유사 선형시간은 로그 시간과 선형시간 사이에 위치한다.

선형 시간보다 성능이 나쁘지만 앞으로 보게 될 많은 다른 복잡도 보다 좋은 성능을 가지고 있다.

 

유사선형 시간 복잡도는 평방 시간 복잡도와 유사한 형태의 곡선을 띄는데 그 곡선이 빠르게 올라가지는 않으므로 대규모의 데이터를 다루는데 더욱 탄력적이다.

 

여기까지 1, 2편을 나눠 알고리즘의 복잡도에 대해서 알아보았다. 지금까지 Big O 표기법으로 나타내는 말이 어떤 말인지 잘 이해하지 못했는데 그래도 이제 개념은 어느정도 이해가 되는 것 같다.

 

다음 챕터부터는 Swift 자료구조에 대해서 더 알아보는 시간을 가져보려고 한다!

 

오늘은 여기까지!