API의 시간 복잡도(Time complexity)에 대해 이해하고 있으면 보다 성능이 우수한 앱을 만들 수 있습니다. 이에 대해서 Swift의 Collection Types의 Method나 Property의 Time complexity에 대해 정리해 보겠습니다. mutating 하는 Method는 Copy on Write를 고려해주셔야 합니다. 기준은 최대한 공식문서를 참고했습니다. 혹시 틀린 점이 있다면 댓글로 알려주시면 감사하겠습니다.
Array
append(_ newElement: Element)
평균 시간 복잡도는 O(1)입니다. 최악의 시간복잡도 O(N)입니다. 최악의 상황은 메모리를 재할당 해야 할 때입니다.(C++ Vector와 유사, exponential로 크기가 증가합니다.)
append(contentsOf:)
평균 시간 복잡도는 O(M)입니다.M은 새로운 Elements의 개수입니다.
insert(_ newElement: Element, at i: Int)
O(N)입니다. i가 마지막 index일 경우, append와 시간 복잡도가 같습니다.
count
O(1)입니다.
subscript(_:)
read는 항상 O(1), write는 일반적으로 O(1)입니다. NSArrary와 brideged 됐을 경우나 다른 arrary와 storage를 공유하고 있을 경우는 O(N)으로 바뀝니다. (Copy on Write)
randomElement()
O(1)입니다.
reserveCapacity(_:)
O(N)입니다.
last
O(1)입니다.
isEmpty
O(1)입니다.
popLast(), removeLast()
O(1)입니다.
remove(at:)
O(N)입니다.
removeFirst()
O(N)입니다.
removeAll(keepingCapacity:)
O(N)입니다.
contains(_:), contains(where:)
O(N)입니다.
allSatisfy(_:)
O(N)입니다.
first(where:), firstIndex(where:), last(where:), lastIndex(where:), firstIndex(of:), lastIndex(of:)
O(N)입니다.
min(), max()
O(N)입니다.
enumerated()
O(N)입니다.
sort(), sorted()
O(N logN)입니다. Swift에선 MergeSort와 InsertionSort를 기반으로 만든 Timsort를 사용합니다.
www.youtube.com/watch?v=2pjUsuHTqHc
reverse()
O(n)입니다.
rereversed()
O(1)입니다. revese()와 시간복잡도가 다릅니다. ReversedCollection을 반환하기 때문입니다. ReversedCollection는 참조 순서를 역순으로 하게 만듭니다.
shuffle(), shuffled()
O(N)입니다.
partition(by:)
O(N)입니다.
swapAt(_:_:)
O(1)입니다.
split(separator:maxSplits:omittingEmptySubsequences:), split(maxSplits:omittingEmptySubsequences:whereSeparator:)
O(N)입니다.
elementsEqual(_:), ==
O(M)입니다. M은 두 sequence length중에 더 작은 length입니다.
Set
subscript(_:)
O(1)입니다
count
O(1)입니다.
contains(_:)
O(1)입니다.
contains(where:)
O(N)입니다.
removeFirst()
평균 O(1), bridged NSSet으로 Wrap되지 않은 경우, 명시되지 않습니다.
firstIndex(of:)
O(1입니다.)
Dictionary
subscript(_:)
O(1)입니다
count
O(1)입니다
contains(where:)
O(N)입니다. contains(_:) method는 없습니다. (key로 바로 참조하면 알 수 있기 때문입니다.)
index(forKey:)
평균 O(1), bridged NSDictionary으로 Wrap된 경우 O(N)입니다.
mapValues(_:)
O(N)입니다.
compactMapValues(_:)
O(M+N)입니다. N은 기존 Dictionary의 크기이고, M은 결과 Dictionary의 크기입니다.
remove(at:), removeValue(forKey:), removeAll(keepingCapacity:)
O(N)입니다.
popFirst()
평균 O(1)입니다.
rereversed()
O(N)입니다.
String
count
O(N)입니다(stackoverflow.com/questions/50568726/what-is-the-bigo-of-swifts-string-count)
ClosedRange
contains(_:) , ~=
O(1)입니다.
Higher-order functions
map, flatMap, compactMap, filter and reduce 는 O(n)입니다.
고찰
Swift를 이용하면서 시간복잡도에 대해 한번 정리해보고 싶었습니다. 참조는 모두 O(1)이며, String의 경우 count property가 시간복잡도가 O(N)이므로
if word.count == 0 //X
if word.isEmpty // Oword의 count가 많을 경우 비효율적인 탐색을 하게되니 isEmpty를 사용해야 합니다. 또한 Array의 contain을 사용할 땐 시간복잡도가 O(N)이므로 Set 자료구조로도 구현이 가능한지 생각해 봐야 합니다.
References
github.com/apple/swift/blob/main/stdlib/public/core/Set.swift
github.com/apple/swift/blob/main/stdlib/public/core/Array.swift
github.com/apple/swift/blob/main/stdlib/public/core/Dictionary.swift
developer.apple.com/documentation/swift
stackoverflow.com/questions/50568726/what-is-the-bigo-of-swifts-string-count
stackoverflow.com/questions/49887447/swifts-map-and-filter-functions-time-complexity
stackoverflow.com/questions/51363653/whats-the-time-complexity-of-swift-reversed
developer.apple.com/documentation/swift/dictionary/order_dependent_operations_on_dictionary
developer.apple.com/documentation/swift/set/order_dependent_operations_on_set
'iOS > Swift' 카테고리의 다른 글
| iOS) Swift에 대한 고찰 (0) | 2021.02.02 |
|---|
