Swift
Collections
Array
Array
Value type 이다.
@frozen public struct Array<Element>
조회
O(n)
append
append(_ newElement: Element)
평균 시간 복잡도
O(1)
최악의 시간복잡도(메모리를 재할당 해야 할 때)
O(N)
append(contentsOf:)
평균 O(M)
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를 공유하고 있을 경우는 Copy on Write로 O(N)으로 변경
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:)
O(N)
firstIndex(where:)
O(N)
last(where:)
O(N)
lastIndex(where:)
O(N)
firstIndex(of:)
O(N)
lastIndex(of:)
O(N)
min(), max()
O(N)
enumerated()
O(N)
sort(), sorted()
O(N logN)
Swift에선 MergeSort와 InsertionSort를 기반으로 만든 Timsort를 사용
reverse()
O(n)
rereversed()
O(1)
revese()와 시간복잡도가 다릅니다.
ReversedCollection을 반환하기 때문입니다.
ReversedCollection는 참조 순서를 역순으로 하게 만듭니다.
shuffle(), shuffled()
O(N)
partition(by:)
O(N)
swapAt(::)
O(1)
split(separator:maxSplits:omittingEmptySubsequences:)
O(N)
split(maxSplits:omittingEmptySubsequences:whereSeparator:)
O(N)
elementsEqual(_:), ==
O(M), M은 두 sequence length중에 더 작은 length.
댓글남기기