Swift Arrayの時間計算量(Time Complexity) チートシート

Swiftを用いたCoding Interviewに向けて、Time Complexityについて整理します。
Arrayでよく利用するmethodを中心に一覧にしましたので、ご参考になればと思います。

:::note info
公式のドキュメントに丁寧に 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.|


:::note info
注釈
- **O(1), O(*k*)** : O(1) if the collection conforms to `RandomAccessCollection` otherwise, 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`インスタンスが、基になるコレクションをラップし、その要素へのアクセスを逆の順序で返すため。