arraylistの要素を検索したい場合は、Big-Thetaは何ですか？

Question

私は最初に配列をソートしてからバイナリ検索を使うことができると思います。 だからO（n^2）。 これは間違いありませんか？

Answer 1

私は配列を最初にソートしてからバイナリ検索を使うことができると思います。だからO（n^2）。あれは正しいですか？

このアプローチの複雑さは、ソートではO（nlogn）、バイナリ検索では検索を行うO（logn）です。全体的なO（nlogn）。

代替案は、O（n）である単純な線形検索ルックアップ（例えば、containsまたはループを使用）です。

バイナリ検索を並べ替えて使用すると、多くの検索で（ソート全体の）並べ替えコストを償却することができます。すなわち一度ソートすると、何度も検索する。

リニア検索よりも優れている場合は、ソートされた構造体をO（nlogn）よりも良く、O（n）よりも良好に検索できるデータ構造を使用する必要があります。
最後に...あなたがこれを行う場合：

• ソート初期のArrayListを。
• バイナリ検索を使用して挿入/削除の正しいポイントを見つけることによってソートされたarraylistを更新します。
• ルックアップにバイナリ検索を使用します。

あなたはO（O（nlogn）はステップ償却ソート付き）（n）は、更新操作及びO（LOGN）ルックアップ要するに

---

で終わるであろう、それは複雑な集合であります最適なものは、アプリケーションの予想される動作に依存します。

---

^{1からTreeSetは（それは重複を排除することを法とする）ことを行うだろう。これは、フードの下に赤黒の二分木を使用します。あなたのデータが実際にセットである場合、O(1)操作を与えるHashSetを考慮する必要があります（ハッシュコード機能が病理学的でない限り）。}