Swiftを用いたCoding Interviewに向けて、Time Complexityについて整理します。
Arrayでよく利用するmethodを中心に一覧にしましたので、ご参考になればと思います。
公式のドキュメントに丁寧に Time Complexityの記載はありますので、
詳しくは公式のドキュメントを参照してください。
https://developer.apple.com/documentation/swift/array
チートシート
| Name | Complexity | Note |
|---|---|---|
| popLast() | O(1) | Removes and returns the last element of the collection. |
| removeFirst() | O(n) | Removes and returns the first element of the collection. |
| removeLast() | O(1) | Removes and returns the last element of the collection. |
| dropFirst() | O(1), O(k) | Returns a subsequence containing all but the given number of initial elements. |
| dropLast() | O(1), O(n) | Returns a subsequence containing all but the specified number of final elements. |
| drop(while:) | O(n) | Returns a subsequence by skipping elements while predicate returns true and returning the remaining elements. |
| prefix() | O(1), O(k) | Returns a subsequence, up to the specified maximum length, containing the initial elements of the collection. |
| prefix(while:) | O(n) | Returns a subsequence containing the initial elements until predicate returns false and skipping the remaining elements. |
| prefix(upto:) | O(1) | Returns a subsequence from the start of the collection up to, but not including, the specified position. |
| prefix(through:) | O(1) | Returns a subsequence from the start of the collection through the specified position. |
| suffix() | O(1), O(n) | Returns a subsequence, up to the given maximum length, containing the final elements of the collection. |
| suffix(from:) | O(1) | Returns a subsequence from the specified position to the end of the collection. |
| Name | Complexity | Note |
|---|---|---|
| map() | O(n) | Returns an array containing the results of mapping the given closure over the sequence's elements. |
| flatMap() | O(m + n) | Returns an array containing the concatenated results of calling the given transformation with each element of this sequence. |
| compactMap() | O(m + n) | Returns an array containing the non-nil results of calling the given transformation with each element of this sequence. |
| filter() | O(n) | Returns an array containing, in order, the elements of the sequence that satisfy the given predicate. |
| reduce() | O(n) | Returns the result of combining the elements of the sequence using the given closure. |
| first() | O(n) | Returns the first element of the sequence that satisfies the given predicate. |
| enumerated() | O(1) | Returns a sequence of pairs (n, x), where n represents a consecutive integer starting at zero and x represents an element of the sequence. |
| min() | O(n) | Returns the minimum element in the sequence, using the given predicate as the comparison between elements. |
| max() | O(n) | Returns the maximum element in the sequence, using the given predicate as the comparison between elements. |
| contains() | O(n) | Returns a Boolean value indicating whether the sequence contains an element that satisfies the given predicate. |
| reverse() | O(n) | Reverses the elements of the collection in place. |
| reversed() | O(1) | Returns a view presenting the elements of the collection in reverse order. |
| sort() | O(n log n) | Sorts the collection in place, using the given predicate as the comparison between elements. |
| sorted() | O(n log n) | Returns the elements of the sequence, sorted using the given predicate as the comparison between elements. |
| swapAt() | O(1) | Exchanges the values at the specified indices of the collection. |
| split() | O(n) | Returns the longest possible subsequences of the collection, in order, that don't contain elements satisfying the given predicate. |
| shuffled() | O(n) | Returns the elements of the sequence, shuffled. |
注釈
-
O(1), O(k) : O(1) if the collection conforms to
RandomAccessCollectionotherwise, O(k), where k is the number of elements to drop from the beginning of the collection. -
O(1), O(n) : O(1) if the collection conforms to
RandomAccessCollection; otherwise, O(n), where n is the length of the collection. - O(n) : n is the length of the collection.
- O(m + n) : n is the length of this sequence and m is the length of the result.
- O(n log n) : n is the length of the collection.
個人的な見解
- removeFirst()は Collectionタイプでは O(1)であるが、Arrayタイプの時はO(n)となる。これはArrayにはindexが付与されており、先頭のElementとremoveした場合残りの全てのElementのIndexをdecrementする必要があるため。
- reversed()は Collectionタイプでは O(n)であるが、Arrayタイプの時はO(1)となる。これはArrayの時は
ReversedCollectionインスタンスが、基になるコレクションをラップし、その要素へのアクセスを逆の順序で返すため。