Big-O表記による異なるデータ構造上の異なる操作の複雑さ

Question

Javaプログラミングでは大きなO表記について読んでいました。次の表は、異なるデータ構造の異なる大きなOを示しています。

http://bigocheatsheet.com/

私の質問は以下のとおりです。

1. 私は、配列内の項目を削除したい場合は、それがO(n^2)のですか？ （検索と削除）
2. スタック内のアイテムを削除する場合は、O(n)ですか？
3. どちらが効果的ですか？それは単一のリンクリストかダブルシングルリストですか？
4. ハッシュテーブルの挿入操作がO(1)またはO(n)の場合はどうなりますか？
5. バイナリ検索ツリーでアイテムを削除したい場合は、O(log(n)*log(n))ですが、挿入はちょうどO(log(n))ですか？

ありがとうございます。

Answer 1

は私があなたの質問に答えてみましょう：

1. いいえ。それはO(n) + O(n) = O(n)です。
2. いいえ、それはO(1)ですが、あなたは1つ、非常にトップの要素にしかアクセスできません。他の要素については、O（n）です。
3. ダブル・シングル・リストは悪くない場合もありますが、時にはより速い場合もありますが、追加の参照用にさらに多くのメモリーが必要です。
4. ベストタイム - まだそのハッシュを持つ要素がないとき、すべての挿入された要素があるモジュロに従って同じハッシュを持つときは最悪です。たとえば、ハッシュ値の3を法とした値を比較し、ハッシュ関数が常にいくつかのkに対して3kの数値を返した場合は、O(n)になります。
5. いいえ、あなたのテーブルによると、それは最悪のケースですO（n）。

もう少しで説明します。

Answer 2

1. 1つの操作を行い、もう一方の操作を行うときには、その複雑さを掛けないでください。最大のものが勝ちます。この場合、O（n）+ O（n）= O（n）
2. スタックには「任意のアイテムを削除する」APIがありますか？基礎となるデータ構造を公開しているが、スタックは通常、要素を「ポップ」する単一の方法を持っています
3. ユースケースは何ですか？
4. hash collisionsの間に何が起こるか調べます。

Answer 3

1. あなたは、配列から項目を削除したい場合は、最初にあなたはそれを検索する必要が（O(n)かかります）、その後、あなたはギャップ（O(n)かかります）を記入する項目をシフトする必要があります。したがって、有効時間の複雑さはO(n)です。
2. スタックから項目を削除する場合は、一番上の要素（スタックデータ構造のプロパティ）のみを削除できます。したがって、それはO(1)で行うことができます。
3. より効果的なリンクリストのタイプは、要件によって異なります。たとえば、メモリを節約したい場合は、余分なポインタ参照を維持するオーバーヘッドのために、二重リンクリストを使用しないことがあります。しかし、両方向でリストをトラバースできるようにするには、二重リンクリストを使用する必要があります。二重リンクリストの実装は、より多くのポインタ操作を実行する必要があるため、少し時間がかかりますが、最後の要素を削除するなどの多くの操作を簡単に実行できます。
4. ハッシュテーブルを使用するのは、O(1)の挿入と検索時間がかかるためです。 O(n)挿入時間は、他のほぼすべてのデータ構造が占めます。 （O(n)クラスは、O(log n),O(1)などを含むクラス）。各チェーンがソートされたリンクリストであるハッシュテーブルでseparate chainingを使用するとします。次に、挿入するたびに、リンクリストを検索して、挿入する正しい位置を見つけ出す必要があります（Insertion Sortと同様）。最悪の場合はO(n)になります。
5. 要素をBSTから削除する必要がある場合は、最初に要素を検索する必要があります（平均ではO(log n)）。削除されたノードをそのinorderの後継者または前任者（）に置き換える必要があります。したがって、効果的な平均ケース削除時間はO(log n)です。