[Algorithm/Swift] Time complexity를 고려한 함수

 

공부하기 좋게 데미안님이 Time complexity를 함수별로 작성해주셔서 가져왔다.

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

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

ClosedRange

contains(_:) , ~=

O(1)입니다.

Higher-order functions

map, flatMap, compactMap, filter and reduce 는 O(n)입니다.

Tip

if word.count == 0 //X
if word.isEmpty // O

word의 count가 많을 경우 비효율적인 탐색을 하게되니 isEmpty를 사용해야 합니다.
또한 Array의 contain을 사용할 땐 시간복잡도가 O(N)이므로 Set 자료구조로도 구현이 가능한지 생각해 봐야 합니다.