[Swift] The Swift Arcade Data Structures and AlgorithmsBootcamp - Big O Nation

다시 기초부터 다지는 느낌으로 Swift로 알고리즘 강의를 들어보면 어떨까 싶어서 듣게 된

Udemy 사이트의 The Swift Arcade Data Structures and AlgorithmsBootcamp

https://www.udemy.com/course/the-swift-arcade-data-structures-and-algorithms-bootcamp/

 

What We Learned

 

1. BigO is the language used to compare performance of algorithms (time and space)

빅O 표현기법은 알고리즘 수행능력을 비교하기 위한 것 ( 수행능력 -> 시간복잡도 & 공간복잡도 )

 

1-1. Constant O(1) / Linear O(n) / Quadratic O(n^2) / Logarithmic O(logn)

 

2. When measuring O(n), always think worst case

O(n)을 계산할 땐, 항상 최악의 경우로 계산

 

3. Can often trade-off time for space

공간복잡도와 시간복잡도 사이에서 절충안을 선택할 수 있음

 

 

Brute Force -> 시간복잡도 O(n^2), 공간복잡도 O(1) 

func commonItemsBrute(_ A: [Int], _ B: [Int]) -> Bool {
    for i in 0..<A.count {
        for j in 0..<B.count {
            if A[i] == B[j] {
                return true
            }
        }
    }
    return false
}

 

Hash Maps / Dictionaries 를 활용하면 -> 시간복잡도 O(n), 공간복잡도 O(n)

func commonItemsHash(_ A: [Int], _ B: [Int]) -> Bool {
    
    var hashA = [Int: Bool]()
    for a in A { 
        hashA[a] = true
    }
    
    for b in B {
        if hashA[b] == true {
            return true
        }
    }
    return false
}

 

Dictionary를 사용했을 때 공간복잡도가 늘어났지만 시간복잡도는 훨씬 줄어들었다

이렇게 시간<->공간 사이의 절충안을 택한다