코딩테스트 - Swift Array, Set, Dictionary 관련 함수 시간 복잡도

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를 사용합니다

 

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)입니다.

https://github.com/apple/swift/blob/main/stdlib/public/core/Set.swift

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)입니다.

https://github.com/apple/swift/blob/main/stdlib/public/core/Dictionary.swift

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)입니다.

 

 

출처:

https://demian-develop.tistory.com/30