Swift Setの時間複雑度.indexOf

Set.indexOfの時間複雑度はどのくらいですか？ documentationは言っていませんし、source代理人は何らかの種類の内部ストレージクラス（_VariantStorage/_VariantSetStorage）のソースを見つけることができません。Swift Setの時間複雑度.indexOf

出典

2016-03-24 phu

CollectionTypeのdocumentationは、O（self.count）であることを示しています。

最悪のシナリオは、Set（または他のコレクション）のすべての要素が等しいかどうかがチェックされるということです。 O（self.count）よりも複雑であることはありません。more

出典

2016-03-24 23:21:05

これはデフォルトの実装に適用されますが、 'Set'は独自の実装を提供します。そして、 'Set.Index'がどのように動作するかによって、' Set'が 'O（1）'の実装を提供できるようになるのは意味があります。 – phu

O（n）は可能であるが保証されていない、実際にはO（n）が最悪のシナリオであることを示唆するハッシュテーブルの複雑さに関するこの回答を見てください：http://stackoverflow.com/questions/9214353/ hash-table-runtime-complexity-insert-search-and-delete –

さらに調査したところ、 '_VariantSetStorage'のソースは実際には同じファイルにあることがわかりました。私はちょうどGYBマクロのために検索でそれを見つけられませんでした。それに基づいて、あなたの答えは技術的に正しいと思いますが、もっと徹底的なバージョンは、ネイティブ 'Set'の' O（1） '、ラップされた' NSSet'の 'O（n）'平均、 'O（n）'は両方とも最悪の場合です（ハッシュ衝突のため）。 – phu

Swift Setの時間複雑度.indexOf

答えて

関連する問題