Kodeco | Swift의 데이터 구조 및 알고리즘 - 복잡성

안녕하세요

데이터 구조 및 알고리즘에 대해서

타 언어를 배울 때 공부했지만

 

또 한 번 더 다루면서 Swift에 좀더 친숙하고 내가 몰랐던

데이터 구조나 알고리즘을 알기위해서 구매를 했습니다

 

kodeco

 

사이트(클릭클릭👆🏻) kodeco에 들어가면 다양한 자료들을 볼 수 있으니 강추 드립니다

강의보단 책이 좋다는 평이 있어서 저도 책으로 구매하였답니다 :)

 

자세히 정리하는 부분은 공개된 부분만 자세히 정리할 예정이며 나머지부분은 짧게 정리할 예정입니다 

 

알고리즘의 성능을 수학적으로 표현이 가능한 표현법이 있습니다

그리고 시간과 공간복잡도를 표현이 가능하구요

실제 러닝타임을 표시하는것보다

데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는게 더 중요하다고 생각이 드는데요

 

왜냐면

적은 양의 데이터로 작업할 때 값을 시간과 공간복잡도가 높더라도 부하가 걸린다는 느낌을

못느낄 수도 있습니다 하지만 데이터가 증가하게된다면??.. 앱을 삭제해 버리는 순간이 다가오겠죠

 

이번 장에서는 Big O 표기에 대해서 알아보고자 합니다

 

시간복잡도

|

적은 양의 데이터의 경우 최신 하드웨어의 속도로 가장 비싼 알고리즘이라도

빠르게 보일 수 있지만

데이터가 증가함에 따라 값비싼 알고리즘 비용이 점점 더 돋보이며.. 위의 말 처럼

앱이나 사이트 자체가 힘들어 질 겁니다

 

시간 복잡도는 입력 크기가 증가함에 따라 알고리즘을 실행하는 데 필요한 시간을 측정합니다

 

 

일정한 시간

Big O 표기

O(1)

|

 

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

 

 매개변수 names 배열의 크기는 실행 시간에 영향을 주지 않고 있습니다

입력 항목이 10개, 10000만 개이든 관계 없이 함수의 첫번째 요소만 출력하고 끝나기 때문에

입력 데이터가 아무리 증가하더라도 알고리즘에 소요되는 시간은 변하지 않는것을 알 수 있습니다

 

배열의 크기가 4인 짧게 만들었지만 1000의 크기의 배열을 만들어서

실행하더라도 동일할것 입니다

timeInterval로 확인해 볼까요?

 

심지어 첫번째가 더 느린걸 확인할 수 있습니다

이렇게 시간이 항상 다르게 나오는 이유는 

현재 실행 중인 프로세스나 다른 작업들이 코드를 실행하는 동안 CPU나 메모리를 차지할 수 있기 때문에 시간에 영향을 미치게됩니다

어쨌든 비슷한게 보이죠??

 

 

그래서 크기와 상관없이 수평으로 나타난다라고 볼 수 있습니다

 

 

선형시간

Big O 표기

O(n)

|

 

names 배열의 크기

4

 

names1 배열의 크기

10000

 

하나씩 출력한다고 했을 때 실행되는 시간을 기록해 보았습니다

 

names 배열을 도는데 걸리는 시간

0.009546995162963867 seconds

 

names1 배열을 도는데 걸리는 시간

1.1053800582885742 seconds

 

 

걸리는 시간을 나눠보면 거의 115배 차이가 나게 됩니다

많이 나죠??

 

이렇게 코드와 시간에서 알 수 있는 점은

 

 

배열의 크기가 증가하면 루프의 반복횟수도 증가하기 때문에

직선 선형 그래프로 증가를 합니다

이 동작을 선형 시간 복잡도라고 합니다

 

그럼 만약에 2개의 루프가 있고 6개의 O(1)메서드를 호출하는 함수는?

O(2n+6)이라는 생각을 할 수 있지만

그냥 단순히 O(n)으로 표기를 합니다

 

2차 시간

Big O 표기

O(n²)

|

n의 제곱이라고 하는 이 시간 복잡도는 입력 크기의 제곱에 비례하여 시간이 걸립니다

 

 

코드에서 보다시피

이중 포문을 사용하고 있기에

 

배열의 크기가 5면 전체 5번을 반복하게 되며

 

10번이면 전체 10번을 반복하게 되며

 

총 25 / 100번이 출력됩니다

 

제곱으로 이루어져 있는걸 확인할 수 있기에

데이터가 크기가 증가하게 되면 알고리즘을 실행하는데 걸리는 시간이

0 -> 1 -> 4 -> 9 -> 16 -> 25 -> 36 ->....이런식으로

급격히 늘어나게 됩니다

 

 

Logarithmic time

|

알고리즘의 시간복잡도를 나타내는 용어입니다

입력 크기 n에 대해 수행 시간이 log(n)에 비례하는 경우를 말하고 있습니다

 

정렬된 정수 배열이 있는 경우 특정  값이 존재하는지 찾는 방법에 대해서 알아보고자 합니다

 

 

배열의 크기가 9인 상수 numbers에서 451이 포함되어있는지에 대한

naiveContains함수를 만들고 호출했습니다

 

코드에서 for문을 통해서 각 요소를 접근하여 451과 요소가 동일한지 유무를 판단하는 코드므로

배열안에 있는 모든 요소에 접근하는 O(n)알고리즘의 방법도 있지만

 

배열이 정렬되어있기 때문에 중간 값을 확인하여 절반을 삭제하며 검사를 할 수 있습니다

 

 

무려 5번만에 찾았다구요??

 

이렇게 중간 값을 찾아서

절반의 값을 찾지 않는 방법이 있습니다

 

이렇게 하는 방법도 있겠지만 개인적으로 반씩 계속 나눠지게끔 만드는 코드도 좋을것 같다라는 생각이 드네요

0~8번 인덱스가 있다면 크기는 9이므로

9 / 2 = 4

451이므로 나머지 배열에서 또 반을 나누는 방식으로 찾는게 더 빠를것 같다라는 생각이 들었습니다

 

log2(n)

 

 

예를 들어 1000의 크기의 데이터면 500개의 비교가 저장되게 됩니다

그래서 점점 수평에 가까워지는걸 볼 수 있습니다

 

이 알고리즘은 소수이지만 이를 사용하게 된다면 시간 단축 효과는 괜찮을것 같습니다

Big O 표기법은 O(log n)으로 표기합니다

 

준선형 시간

|

선형 시간보다 성능은 떨어지지만 2차 시간 (제곱)보단 성능이 훨씬 좋습니다

 

일반적인 알고리즘 중 하나입니다

✏️예) 정렬(sort)

 

준선형 시간 복잡도에 대한 Big O 표기법은

O(n log n)로 표기됩니다

 

시간 복잡도 비교

|

1부터 n까지 숫자의 합을 구하는 코드를 작성해보겠습니다

 

//10000번이 반복된 후 반환하기 때문에
//⭐️시간복잡도에 대한 Big O : O(n)
func sumFromOne(upto n: Int) -> Int {
  var result = 0
  for i in 1...n {
    result += i
  }
  return result
}


sumFromOne(upto: 10000)

func sumFromOne1(upto n: Int) -> Int {
  //표준 라이브러리에서 컴파일된 코드를 호출하기 때문에 더 빠르게 실행됩니다
  //하지만 시간복잡도는 + 메서드 시간을 호출하므로
  //O(n reduce)임을 알 수 있습니다
  //sumFromOne과 동일하지만 컴파일된 코드이므로 상수가 더 작습니다
  (1...n).reduce(0, +)
}

sumFromOne1(upto: 10000)


func sumFromOne2(upto n: Int) -> Int {
 //Fredrick Gauss가 발견된 식
 //⭐️시간복잡도에 대한 Big O : O(1)
 (n + 1) * n / 2
}

sumFromOne1(upto: 10000)

 

 

 

 

공간 복잡도

Space complexity

 

|

공간 복잡도는 함수가 실행되는 동안 추가로 필요한 메모리 공간을 이야기합니다

 

 

위 함수에서 사용하는 array.sorted()는  array 매개변수에 들어가는 배열과 동일한 크기의 새로운 배열을 생성하기 때문에

printSorted(_ 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 {    //array 요소에 min값과 동일하면 값을 출력 
      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
    //배열에 요소에 접근하여 currentValue와 같은 값을 찾아 출력하고 출력된 개수를 증가시킴
    for value in array {
      if value == currentValue {
        print(value)
        currentCount += 1
      }
    }

    // 6
    //minvalue에 현재출력된 값으로 갱신하고 다음 반복해서 이 값을 기준으로 더 큰 값을 찾게됨
    minValue = currentValue
  }
}

//시간복잡도
O(n)×O(n)=O(n2)
//공간복잡도
O(1)

 

위의 알고리즘은 몇 가지 변수를 추적하기 위해 메모리를 할당하기 때문에

공간 복잡도는 O(1) 입니다

 

기타 표기법

|

Big O 표기법을 사용하여 알고리즘을 평가 하지만

다른 표기방법도 존재합니다

 

Big Omega

알고리즘의 최상의 런타임을 측정하는데 사용됩니다

최상의 경우를 얻는 것이 종종 불가능하기 때문에

Big O만큼 유용하지 않습니다

 

Big Theta

최상의 경우와 최악의 경우가 동일한 알고리즘의 런타임을 측정하는데 사용됩니다

 

 

 

❤️혹시나 잘못된 부분이 있다면 댓글로 알려주면 감사하겠습니다❤️

 

 

 

 

참고

https://www.kodeco.com/books/data-structures-algorithms-in-swift

Data Structures & Algorithms in Swift