0

このコードの順序の複雑さが n(logn) であるかどうかを確認できますか? そうでない場合は、あなたの答えを説明してもらえますか? 助けてくれて本当にありがとう

  public static boolean isDuplicate(String s){
        char[] sArray = s.toCharArray();
        for(int i=0;i<sArray.length/2;i++){
            for(int j=sArray.length/2+1;j<sArray.length;j++){
                if(sArray[i] == sArray[j])
                    return true;
            }
        }
        return false;
    }
4

1 に答える 1

1

いいえ、そうではありません。それは O(n^2) です。なぜなら、外側のループで配列全体を反復処理しており、 の値ごとiに、内側のループでも配列全体を反復処理しているためです。配列を 2 つに分割しても、順序の複雑さは変わりません。

O(n*log(n)) アルゴリズムで重複を見つけたい場合は、配列を並べ替えて、次のように隣接する場所で重複を確認できます。

public static boolean isDuplicate(String s){
    char[] sArray = s.toCharArray();
    Arrays.sort(sArray); // O(n*log(n))
    for (int i=0; i<sArray.length-1; i++) // O(n)
        if (sArray[i]==sArray[i+1])
            return true;
    return false;
}

さらに良いことに、 a を使用してHashSet、 O(n) で重複を見つけることができます。

public static boolean isDuplicate(String s){
    HashSet<Character> alreadySeenChars = new HashSet<Character>();
    char[] sArray = s.toCharArray();
    for (int i=0; i<sArray.length; i++) { // O(n)
        if (alreadySeenChars.contains(sArray[i])) // O(1)
            return true;
        alreadySeenChars.add(sArray[i]); // O(1)
    }
    return false;
}
于 2013-06-04T04:21:17.847 に答える