1

私はJavaデータ構造コースのATMを受講しています。私の課題の1つは、選択したデータ構造を選択し、スペルチェッカープログラムを作成するように求めています。現在、さまざまなデータ構造のパフォーマンスをチェックしています。

私はツリーセットのAPIに行きました、そしてこれはそれが言うことです...「この実装は基本的な操作（追加、削除、そして含む）のために保証されたlog（n）時間コストを提供します。」

これにはremoveAll（）が含まれますか？

他にどのように私はこれを理解することができますか

前もって感謝します

4

2 に答える 2

2

removeAll（）は含まれませんが、polkageistの答えに同意しない必要があります。removeAll（）は、実装によっては一定時間で実行される可能性がありますが、実行は線形時間で行われる可能性が最も高いようです。

NlogNは、それがほとんど最悪の方法で実装された場合になると思います。各要素を削除する場合は、要素を検索する必要はありません。持っている要素はすべて削除する必要があるため、検索する必要はありません。

于 2011-11-09T20:53:36.407 に答える
0

いいえ。サイズkの引数コレクションの場合、removeAll（）の最悪の場合の上限は、もちろんO（k * log n）です。これは、引数コレクションに含まれる各要素をツリーセットから削除する必要があるためです（これには少なくともそれらを検索する必要があります）、この検索のそれぞれはlognのコストをもたらします。

于 2011-11-09T00:00:04.730 に答える