remove()JavaのPriorityQueueクラスの関数の複雑さ（big-oh）は何ですか？文書化されているものはどこにも見つかりません。要素を削除してからツリーを再シャッフルする前に要素を見つける必要があることを考えると、O（n）だと思います。しかし、私は反対し、それがO（logn）だと思う他の人を見てきました。何か案は？
質問する
51900 次
4 に答える
52
混乱は、実際には「削除」機能によって引き起こされます。Java には、2 つの削除関数があります。
remove() -> これは head/root を削除するためのもので、O(logN) の時間がかかります。
remove(Object o) -> 任意のオブジェクトを削除します。このオブジェクトの検索には O(N) 時間がかかり、削除には O(logN) 時間がかかります。
于 2016-08-23T04:54:24.907 に答える
39
remove の複雑さは O(N) です。これは、contains の複雑さが O(N) であるためです (Java の優先度キュー クラス内)。
独自のプライオリティ キューの実装でこれを O(logN) にする方法の 1 つは、プライオリティ キュー内の値からキュー内の位置へのマッピングを維持する HashMap のような補助データ構造を維持することです。したがって、いつでも、任意の値のインデックス位置を知ることができます。
この変更は、既存の操作の実行時間には影響しないことに注意してください。ヒープ化操作中にマッピングを更新するだけで済みます。
于 2014-02-28T05:29:42.933 に答える
10
Oracle のドキュメントによると、「実装に関する注意: この実装は、エンキューおよびデキュー メソッド (offer、poll、 remove() 、および add) にO(log(n))時間を提供します。remove (Object) および contains(Object) には線形時間を提供します。 ) メソッド; 検索メソッド (ピーク、要素、およびサイズ) の一定時間。"
于 2015-09-22T12:03:55.657 に答える