[iOS 10주차] 코드카타: 시간복잡도 퀴즈

Q1.

func getFirstScore(scores: [Int]) -> Int? {
    return scores.first
}

O(1)

---

Q2.

func sumAllScores(scores: [Int]) -> Int {
    var total = 0
    for score in scores {
        total += score
    }
    return total
}

O(n)

---

Q3.

func findPairs(numbers: [Int], target: Int) -> [(Int, Int)] {
    var pairs: [(Int, Int)] = []
    
    for i in 0..<numbers.count {
        for j in (i+1)..<numbers.count {
            if numbers[i] + numbers[j] == target {
                pairs.append((numbers[i], numbers[j]))
            }
        }
    }
    return pairs
}

O(n^2)

---

Q4.

func binarySearch(_ numbers: [Int], _ target: Int) -> Int? {
    var left = 0
    var right = numbers.count - 1
    
    while left <= right {
        let mid = (left + right) / 2
        if numbers[mid] == target {
            return mid
        } else if numbers[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return nil
}

O(logn)

---

Q5.

func mergeSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else { return array }
    
    let mid = array.count / 2
    let left = mergeSort(Array(array[..<mid]))
    let right = mergeSort(Array(array[mid...]))
    
    return merge(left, right)
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var result: [Int] = []
    var leftIndex = 0
    var rightIndex = 0
    
    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] <= right[rightIndex] {
            result.append(left[leftIndex])
            leftIndex += 1
        } else {
            result.append(right[rightIndex])
            rightIndex += 1
        }
    }
    
    result.append(contentsOf: left[leftIndex...])
    result.append(contentsOf: right[rightIndex...])
    
    return result
}

O(n logn)

코드 분석

func mergeSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else { return array } // Base case: 배열 크기가 1 이하일 때 정렬 완료
    
    let mid = array.count / 2
    let left = mergeSort(Array(array[..<mid]))  // 왼쪽 절반 분할
    let right = mergeSort(Array(array[mid...])) // 오른쪽 절반 분할
    
    return merge(left, right)                  // 병합 과정
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var result: [Int] = []
    var leftIndex = 0
    var rightIndex = 0
    
    // 두 배열을 병합
    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] <= right[rightIndex] {
            result.append(left[leftIndex])
            leftIndex += 1
        } else {
            result.append(right[rightIndex])
            rightIndex += 1
        }
    }
    
    // 나머지 요소 추가
    result.append(contentsOf: left[leftIndex...])
    result.append(contentsOf: right[rightIndex...])
    
    return result
}

시간 복잡도 분석

1. 분할 단계 (Divide)

• 배열을 반으로 나눈다. 각 분할은 O(1)의 작업으로 이루어진다.
• 배열의 크기가 n이라면, 이를 n/2, n/4, n/8로 계속 나누며 총 log n 단계가 걸린다.

2. 병합 단계 (Conquer & Combine)

• 나눠진 배열들을 병합하면서 정렬한다.
• 병합 과정에서는 두 배열의 요소를 비교하며 새로운 배열에 추가한다.
  • 두 배열의 합이 n인 경우 병합에 걸리는 시간은 O(n)이다.
• 병합 과정은 배열을 나눌 때마다 이루어지므로, 각 레벨에서 병합에 필요한 총 시간은 배열 전체 크기 n에 비례한다.

3. 전체 복잡도 계산

• 분할 단계: O(log n) (재귀 깊이)
• 병합 단계: 각 단계마다 O(n), 총 log n 단계만큼 수행된다.
• 전체 시간 복잡도는: T(n) = O(n log n)

---

병합 정렬의 공간 복잡도

1. 추가 메모리 사용:
   • 병합 단계에서 정렬된 새 배열을 생성하므로, 추가 메모리 O(n)이 필요하다.
2. 재귀 호출 스택:
   • 최대 log n 깊이의 재귀 호출이 발생하므로, 재귀 스택 공간이 O(\log n)만큼 추가로 필요하다.

최종적으로, 병합 정렬의 공간 복잡도는: O(n).

---

병합 정렬의 특성

• 장점:
  • 최악의 경우에도 항상 O(n log n)의 성능을 보장합한다.
  • 안정 정렬(Stable Sort): 동일한 값의 상대적 순서를 유지한다.
• 단점:
  • 배열 크기 n만큼 추가 메모리를 필요로 하므로, 공간 효율성이 낮다.

---

Q6.

func findCommonElements(in arrays: [[Int]]) -> Set<Int> {
    guard let first = arrays.first else { return [] }
    
    var result = Set(first)
    for array in arrays {
        result = result.intersection(Set(array))
    }
    return result
}

O(k · m)

코드 분석

func findCommonElements(in arrays: [[Int]]) -> Set<Int> {
    guard let first = arrays.first else { return [] }  // 첫 번째 배열을 가져옴
    
    var result = Set(first) // 첫 번째 배열을 기준으로 시작
    for array in arrays {
        result = result.intersection(Set(array)) // 다른 배열과 교집합 계산
    }
    return result
}

변수 정의

• k : 입력 배열의 개수 (arrays.count).
  • arrays는 이차원 배열이므로, 각 배열을 독립적으로 처리해야 하는 횟수를 나타낸다.
• n : 모든 배열에 포함된 총 요소 수.
  • 예를 들어, [[1, 2], [3, 4, 5], [6]]라면 n = 6.
• m : 각 배열의 평균 크기.
  • m = n / k 로 계산할 수 있다. 예를 들어, n = 6, k = 3이면 m = 2.

---

시간 복잡도 분석

1. 첫 번째 배열로 초기화

• Set(first)로 첫 번째 배열을 집합으로 변환하는 데 걸리는 시간:
  • O(m), 여기서 m은 첫 번째 배열의 크기이다.

2. 교집합 연산

• 각 교집합 계산의 시간 복잡도:
  • intersection(Set(array))의 시간 복잡도는 두 집합 중 작은 집합의 크기에 비례합니다.
  • 최악의 경우, 교집합 연산은 O(m) 시간 동안 수행된다.
• 전체 교집합 반복:
  • 배열의 개수 k에 대해 교집합 연산을 반복한다.
  • 최악의 경우 k - 1번 교집합 연산을 수행하며, 각 연산은 평균적으로 O(m) 시간이 걸린다.

---

총 시간 복잡도

• 첫 번째 배열 초기화: O(m)
• 교집합 반복: (k - 1) * O(m)
• 전체: O(m) + O((k - 1) · m) = O(k · m)

---

특수한 경우

1. 모든 배열의 크기가 동일한 경우:

   • 각 배열의 크기가 m, 배열의 개수가 k라면, 총 요소 수 n = k · m.
   • 이 경우, 복잡도는 O(k · m) = O(n)으로 간단히 표현된다.

2. 배열의 크기가 불균형한 경우:

   • 배열의 크기가 매우 다르면, 교집합 계산 시 작은 배열이 연산을 지배한다.
   • 최악의 경우, 모든 배열의 합이 n일 때 복잡도는 여전히 O(k · m) = O(n)이다.

3. 빈 배열 포함:

   • 빈 배열이 있으면, 결과가 즉시 빈 집합이 되므로 O(1) 시간에 종료된다.

---

시간 복잡도 최종 표현

• 일반적으로: O(k · m)
• 또는 O(n), 여기서 n은 모든 요소의 총합.

---

Q7.

func fibonacci(_ n: Int) -> Int {
    if n <= 1 {
        return n
    }
    return fibonacci(n - 1) + fibonacci(n - 2)
}

O(2^n)

재귀 호출 트리

fibonacci(n) 함수는 다음과 같은 호출 트리를 만든다:

예: fibonacci(5) 호출 트리

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3)
│   │   ├── fibonacci(2)
│   │   │   ├── fibonacci(1)
│   │   │   └── fibonacci(0)
│   │   └── fibonacci(1)
│   └── fibonacci(2)
│       ├── fibonacci(1)
│       └── fibonacci(0)
└── fibonacci(3)
    ├── fibonacci(2)
    │   ├── fibonacci(1)
    │   └── fibonacci(0)
    └── fibonacci(1)

호출 트리 특징:

1. 중복 계산 발생:

   • 예를 들어, fibonacci(3)은 두 번 호출되고, fibonacci(2)는 세 번 호출된다.
   • 이러한 중복 계산은 트리가 커질수록 기하급수적으로 늘어난다.

2. 노드 수:

   • 호출 트리는 이진 트리처럼 동작하며, n번째 호출에서 재귀적으로 2^n에 가까운 노드가 생성된다.

---

시간 복잡도 계산

1. 재귀 호출의 횟수:

   • n번째 피보나치 수를 계산하기 위해, 트리의 각 레벨에는 2^k개의 노드가 생성된다. k은 트리의 깊이이다.
   • 트리의 높이는 n이므로, 전체 노드 수는 대략 2^n에 비례한다.

2. 각 호출의 작업량:

   • 각 호출은 O(1)의 상수 시간 작업(덧셈 및 비교)만 수행한다.

3. 최종 시간 복잡도:

   • 노드 수에 따라 계산 작업이 이루어지므로 전체 시간 복잡도는 지수 시간에 해당하는 O(2^n)이다.

---

개선 방법: 동적 프로그래밍

재귀 호출의 중복 계산을 제거하면 시간 복잡도를 크게 줄일 수 있다.

예: 메모이제이션을 사용한 동적 프로그래밍

var memo = [Int: Int]()

func fibonacci(_ n: Int) -> Int {
    if n <= 1 {
        return n
    }
    if let result = memo[n] {
        return result
    }
    let result = fibonacci(n - 1) + fibonacci(n - 2)
    memo[n] = result
    return result
}

• 시간 복잡도:O(n)
  • 한 번 계산된 값은 memo에 저장되므로, 각 피보나치 수는 한 번만 계산된다.

---

결론

1. 기존 재귀 구현:

   • 시간 복잡도: O(2^n)
   • 중복 계산으로 인해 비효율적이다.

2. 메모이제이션 사용:

   • 시간 복잡도: O(n)
   • 효율적이며 실용적인 방법이다.