2

私はこの質問を読んでいました。選択した回答には、次の 2 つのアルゴリズムが含まれています。最初の時間計算量が O(ln(n)) である理由がわかりませんでした。最悪の場合、配列に重複が含まれていない場合、n 回ループし、2 回目もループします。私は間違っていますか、それとも何か不足していますか? ありがとうございました

1) より高速な (極限での) 方法

これはハッシュベースのアプローチです。オートボクシングの料金を支払わなければなりませんが、それは O(n2) ではなく O(ln(n)) です。進取の気性に富んだ人なら、原始的な int ベースのハッシュ セットを探しに行くでしょう (Apache や Google Collections にはそのような機能があると思います)。

boolean duplicates(final int[] zipcodelist)
{
  Set<Integer> lump = new HashSet<Integer>();
  for (int i : zipcodelist)
  {
    if (lump.contains(i)) return true;
    lump.add(i);
  }
  return false;
}

2)ユイルに頭を下げる

多かれ少なかれO（n）ソリューションについては、HuyLeの回答を参照してください。これには、いくつかの追加手順が必要だと思います。

static boolean duplicates(final int[] zipcodelist) {    
    final int MAXZIP = 99999;    
    boolean[] bitmap = new boolean[MAXZIP+1];    
    java.util.Arrays.fill(bitmap, false);    

    for (int item : zipcodeList)
        if (!bitmap[item]) bitmap[item] = true;
        else return true;    
    }

    return false; 
}
4

1 に答える 1

2

最初のソリューションでは、郵便番号リスト全体を走査する必要があり、各郵便番号の処理は O(1) の予想時間の複雑さであるため、予想される複雑さは O(n) である必要があります。

HashMap への挿入が再ハッシュをトリガーする可能性があることを考慮しても、複雑さは依然としてO(1)です。Java HashMap とリンクの仮定との間に関係がない可能性があるため、これは少し不正確ですが、可能であることを示すためにあります。

HashSetのドキュメントから:

このクラスは、ハッシュ関数がバケット間で要素を適切に分散することを前提として、基本的な操作 (追加、削除、含む、およびサイズ)に対して一定時間のパフォーマンスを提供します。

正しく分析された 2 番目の解 O(n) についても同じです。

（トピック外のメモですが、元の投稿に見られるように、 BitSet は array よりも高速です。これは、8booleanが 1 にパックされbyte、メモリの使用量が少ないためです）。

于 2012-06-23T02:26:45.583 に答える