1

私は決勝戦を検討していますが、次の問題に遭遇しました:

バイナリ ヒープには、デフォルトで優先キュー セマンティクスがあります。要素を n 回挿入すると、「消える」前に n 回削除する必要があります。代わりにセマンティクスが設定されたバイナリ ヒープを実装するとします。この場合、挿入操作と削除操作はどれくらい速くなりますか?

(a) 挿入: O(n) 削除: O(logn)

(b) 挿入: O(log n) 削除: O(n)

(c) 挿入: O(log n) 削除: O(log n)

(d) 挿入: O(1) 削除: O(n2)

(e) 上記のいずれでもない。

優先キュー セマンティクスで実装されたヒープに挿入するには、O(logn) になり、削除も同様です。ただし、セットの場合、挿入と削除はセット自体の多くの要因に依存します。答えはどうあるべきだと思いますか。

4

2 に答える 2

2

セットのセマンティクスが何を指すのかは完全には明らかではありませんが、作成者はプロパティを意味している可能性があります

A ∪ {x} ∪ {x} = A ∪ {x}

つまり、すでにセットにある要素を追加しても、(観察可能な) 効果はありません。

これを行う簡単な方法は、挿入時に重複をチェックすることです。ただし、通常のバイナリ ヒープでは、任意の要素を削除するには O(n) かかり、明らかにかなり遅いです。

新しい値が表示されるまで削除を繰り返すことにより、最小の要素を削除する際に重複を排除するのがより賢明なアイデアかもしれません。これには O(k log n) が必要です。ここで、k は取得したノードの重複の数です。k が定数であることがわかっている場合、これは O(log n) です。ただし、最悪の場合は k = n であり、最悪の場合の時間計算量は O(n log n) になります。ただし、代わりに償却された時間の複雑さを測定すると、このアルゴリズムは挿入と削除で O(log n) を達成します。

ヒープの代わりにバランスのとれた二分探索木を使用することで、挿入と削除の最悪の場合の時間計算量 O(log n) を達成することができます。ただし、これが「ヒープ」と見なされるかどうかは明確ではありません。

要約すると、考えられる答えは次のとおりです。

  • O(n), O(log n) : やや素朴なヒープ
  • O(log n), O(n log n) : 調整された実際のヒープ、最悪の場合の時間の複雑さ
  • O(log n), O(log n) : 調整された実際のヒープ、償却された時間の複雑さ
  • O(log n), O(log n) : ヒープを装った平衡二分探索木

つまり、質問をどのように解釈するかによって、正しい答えが異なります。

于 2016-12-18T03:28:45.333 に答える
2

insert: O(n) remove: O(log n) と言うでしょう。セット内の重複アイテムは許可されておらず、重複アイテムを挿入しようとする試みは無視されるべきであり、ヒープは完全に埋められた二分木であるため (下を除いて)、検索するセットに挿入したい場合(項目) 見つかった場合は、挿入する以外に何もしないため、検索と挿入の両方で挿入に O(n) かかる場合があります (最大で log n 回まで浸透する可能性があります)。deleteMin には o(log n) 時間の計算量があります

于 2016-12-18T02:20:43.563 に答える