現在、次のアルゴリズムの複雑な時間を特定して理解するのに苦労しています。
背景: ファイルのリストがあり、それぞれに候補 ID のリストが含まれています。ファイルの数とその中の候補の数の両方が固定されていません。
各ファイルを読み取り、すべての一意の候補 Id をハッシュセットに追加することを担当するアルゴリズムの時間の複雑さをどのように計算しますか?
ありがとう。
1 に答える
0
私はアミットが言ったことを繰り返しているので、それがあなたに明らかであるならば、彼に賛成票を与えてください-私はその説明が少し混乱していると思います。
平均的な複雑さはO（n）です。ここで、nは（すべてのファイルからの）候補の総数です。したがってa、それぞれに候補があるファイルがある場合b、かかる時間はに比例しa * bます。
これは、問題を解決する最も簡単な方法は、すべてのデータをループしてセットに追加することであるためです。セットは必要に応じて重複を破棄します。
すべての値のループには、値の数（つまり、O（n）部分）に比例した時間がかかります。ハッシュセットに値を追加するには、一定の時間（またはO（1））がかかります。これはエントリごとの一定時間であるため、全体の時間はO（n）のままです。
ただし、ハッシュセットには奇妙な最悪の場合の動作があります。一部の（異常な）場合には、コンテンツのサイズに比例して時間がかかります。したがって、最悪の場合、値を追加するたびにO（m）の作業量が必要になります。ここで、mはセット内のエントリの数です。
ここで、mは（おおよそ-ゼロから始まり、最大で...）個別の値の数です。したがって、2つの一般的なケースがあります。
さらに読むにつれて個別の候補の数が増える場合（たとえば、ファイルの90％は常に新しい候補です）、mはnに比例します。つまり、各候補を追加する作業はnに比例して増加します。したがって、合計作業量はn ^ 2に比例します（各候補に対してnに比例して作業を行い、n人の候補者がいるため）。したがって、最悪の場合はO（n ^ 2）です。
個別の候補の数が実際に固定されている場合、ファイルをどんどん読むと、既知の候補でいっぱいになる傾向があります。その場合、セットに挿入するための余分な作業は一定です（一意の候補に対して一定の回数だけ奇妙な動作が発生します-nに依存しません）。その場合、nがどんどん大きくなってもセットのパフォーマンスが悪化し続けることはないため、最悪の場合の複雑さはO（n）のままです。
于 2012-04-29T01:18:09.217 に答える