13

Javaの.equals演算子の時間計算量（big O）は、2つの文字列に対してどのようなものであるのか疑問に思いました。

基本的に、stringOne.equals（stringTwo）を実行した場合、これはどの程度うまく機能しますか？

ありがとう。

4

3 に答える 3

18

ここでの他の答えは単純すぎます。

一般に、2 つの異なる文字列が等しいことを証明するには、各文字を比較するO(n)必要がある場合があります。

ただし、これは最悪のケースにすぎません。equals()平均的/典型的なケースでは、メソッドがこれよりもはるかに優れたパフォーマンスを発揮できることを意味する多くのショートカットがあります。

  • 文字列が同一でO(1)ある場合です。それらは同じオブジェクトであるため、定義上等しいため、結果はtrueです
  • それは、2 つの文字列が等しくないO(1)ことを証明できる、事前に計算されたハッシュコードをチェックできるかどうかです(明らかに、多くの文字列が同じハッシュコードにハッシュされるため、2 つの文字列が等しいことを証明することはできません)。
  • これO(1)は、文字列の長さが異なる場合です (文字列が等しくなることはあり得ないため、結果は false です)。
  • 文字列が等しくないことを証明するには、1 つの異なる文字を検出するだけで済みます。したがって、ランダムに分散された文字列の場合、実際にはO(1)2 つの文字列を比較するのにかかる時間は平均です。文字列が完全にランダムでない場合、結果はデー​​タ分布に応じて、その中間のどこかにある可能性がありO(1)ますO(n)。

ご覧のとおり、正確なパフォーマンスはデータの分布によって異なります。

それとは別に、これは実装に依存するため、正確なパフォーマンス特性は使用する Java のバージョンに依存します。ただし、私の知る限り、現在の主要な Java 実装はすべて上記の最適化を行っているため、文字列のequals()パフォーマンスはかなり高速であると期待できます。

最後のトリック: String のインターンを使用すると、等しいすべての String が同じオブジェクト インスタンスにマップされます。次に、 であることが保証されている の代わりに、オブジェクト IDの非常に高速な==チェックを使用できます。このアプローチには欠点があります (多くの文字列をインターンする必要があり、メモリの問題が発生する可能性があり、このスキームで使用する予定の文字列をインターンすることを厳密に覚えておく必要があります) が、状況によっては非常に便利です。equals()O(1)

于 2014-02-26T03:21:34.947 に答える
14

最悪のケースは O(n) ですが、2 つの文字列が同じオブジェクトの場合は O(1) です。

(ただし、この場合、n は、文字列の合計の長さではなく、最初の文字から始まる 2 つの文字列内の一致する文字の数を指します)。

于 2013-01-27T21:07:41.500 に答える