重複する文字列の複雑さを検索する

Question

重複する要素を見つけてブール値を返すメソッドを書くタスクがあります。

以下のコードは私が持っているものです。

import java.util.ArrayList; 
import java.util.List; 

public class DuplicateEle { 
    public static void main(String args[]) { 
     String[] arr = { "hello", "hi", "hello", "howru" }; 
     DuplicateEle de = new DuplicateEle(); 
     for (int i = 0; i < arr.length; i++) { 
      boolean isDup = de.isDuplicate(arr[i]); 
      System.out.println(arr[i]+" is duplicate :" +isDup); 
     } 
    } 

    List<String> dList = new ArrayList<String>(); 

    private boolean isDuplicate(String str) { 
     boolean isDup = false; 
     if (dList.contains(str)) { 
      isDup = true; 
     } else 
      dList.add(str); 
     return isDup; 
    } 

} 

期待どおりに動作します。 出力：

hello is duplicate :false 
hi is duplicate :false 
hello is duplicate :true 
howru is duplicate :false 

上記のコードの時間の複雑さを確認したいと思います。私は時間の複雑さのチュートリアルを調べて、このように動作する方法について調べていますone。

上記のコードを入力して、時間の複雑さの仕組みを理解してもらえますか？

ありがとうございます！

Answer 1

コードが複雑すぎるため、HashSet<String>を使用してください。一意性が保証され、要素が既にセットに含まれていたかどうかが返されます。それだけで、その後に等しく、完全な「高価」を行うためにequalsを使用する必要が、バケツを見つけるために、文字列のハッシュintを使用するようHashSetを使用して

public class DuplicateEle { 
    public static void main(String args[]) { 
     Set<String> seen = new HashSet<>(); 
     String[] arr = { "hello", "hi", "hello", "howru" }; 

     for (String word : arr) { 
     boolean unique = seen.add(word); 
     System.out.printf("%s is duplicate: %b%n", word, !unique); 
     } 
    } 
} 

は非常に効率的です。

Answer 2

nはチェックされる要素の数であり、mは最も長い単語のサイズです。したがって、要素の配列を調べ、各要素について、その要素がdListであるかどうかをチェックします。

開始時には、その空であり、時間とともに、要素を追加します。だから、質問は、どのくらい速い方法containsです。 ArrayListのソースコードを見ると、配列を通り、各要素がequalであることが確認できます。これは、最後から始まる各文字をチェックすることによって行われます（最初は等しいサイズかどうかをチェックします） 。

最悪の場合は、すべての要素が等しいサイズで、最初の要素が異なる場合です。したがって、最初の要素では何もしないので、基本操作は1とカウントされます。手順2では、手順3で1回、2回の確認などを行い、手順nでn-1回のチェックを行います。

0+1+2+...+n-1 = n(n-1)/2 

は今、最悪のシナリオは、各要素が同じ大きさであり、彼らが最初の要素で異なっているので、あなたは、サイズmの別のループを持っている：だから、あなたが持っています。ここで、mは、文字列（末尾）の異なるcharの位置の平均文字列サイズまたは統計的期待値を表すこともできます。

したがって、O(mn^2)ですが、mにいくつかのランダム性があるとすれば、Ω(n^2)と言います。

しかし、私はあなたのために良いニュースを得ました。 HashSetを使用すると、より速い方法があります。 dListをいくつかのHashSetで変更し、最初のリストを調べるときに各要素を配置する必要があるので、各要素のチェックはO(1)で行われます。つまり、全体の速度はO(n)になります。