0

数値が特定の数値セットの因数であるかどうかをすばやく判断できるアルゴリズムはありますか?

たとえば、12is は因数ですが[24,33,52]5is ではありません。

線形検索よりも優れたアプローチはありますO(n)か? セットには数百万の要素が含まれます。数を見つける必要はありません。trueまたはfalse結果だけです。

4

7 に答える 7

1

多数の数値が定数リストに対してチェックされる場合、プロセスを高速化するための 1 つの可能なアプローチは、最初にリスト内の数値を素因数分解することです。次に、リストのメンバーを辞書に入れ、素因数をキーにします。次に、数値 (潜在的な要因) が来ると、まずそれを素因数に因数分解し、構築された辞書を使用して、その数値が潜在的に特定の数値の倍数になる可能性のある数値の因数であるかどうかを確認します。

于 2012-05-08T11:13:07.210 に答える
0

定数セットに対して多くの潜在的な要因をテストする場合、セットの 1 つの要素が他の 2 つの要素の倍数である場合、それは無関係であり、削除できることを認識する必要があります。このアプローチは、エラトステネスのふるいとして知られる古代のアルゴリズムのバリエーションです。膨大な数の候補をテストする場合、起動時間を実行時間と交換します。

  1. セット内の 1 より大きい最小の数を選択します
  2. それ自体を除いて、その数の倍数をセットから削除します
  3. 次に小さい数に対して 2 を特定の反復回数繰り返します。反復回数は、起動時間とのトレードオフによって異なります

これで、徹底的にテストするためのはるかに小さなセットが残されました。これを効率的に行うには、リンクリストのように O(1) の削除を許可するセットのデータ構造が必要な場合、または単に「削除された」要素をゼロに置き換えてからゼロ以外の要素を新しいコンテナーにコピーする必要があります。

于 2012-05-08T11:36:16.260 に答える
0

検索するセットが固定されているため、検索のためにセットを整理するのに費やす時間は、十分に費やされます。メモリ内のセットを取得できる場合は、バイナリ ツリー構造がうまく適合することを期待しています。平均して、バイナリ ツリー内の要素を検索することはO(log n)操作です。

セット内の数値が範囲全体に均等に分散されていると信じる理由がある場合は[0..10^12]、メモリ内の並べ替えられたセットのバイナリ検索を、バイナリ ツリーの検索と同様に実行する必要があります。一方、セット (またはセットのサブセット) の中央の要素が、セット (またはサブセット) に含まれる範囲の中央値に近いと予想されない場合は、バイナリ ツリーの方が優れていると思います。 (実用的な)パフォーマンス。

セット全体をメモリに取得できない場合は、メモリに収まるチャンクに分解し、それらのチャンクをディスクに保存するのがおそらく最善の方法です。セットのルート ブランチと上位ブランチをメモリに格納し、それらを使用してディスクにインデックスを作成します。メモリに保持されるツリーの部分の深さは、自分で決定する必要がありますが、ルートと 2 レベルのブランチ以上のものが必要で、ディスク上に 8 つのチャンクが必要な場合は驚くでしょう。

もちろん、これは問題の一部を解決するだけで、特定の数値がセット内にあるかどうかを調べます。与えられた数がセット内の任意の数の因数であるかどうかを本当に調べたいとします。コメントで提案したように、セット内の数値を因数分解することに基づくアプローチは絶望的であり、多項式時間を超える予想実行時間が得られると思います。

問題のこの部分には逆にアプローチします。指定された数の倍数を生成し、それぞれを検索します。セットに10^7要素がある場合、指定された数にはセット内のN(10^7)/N倍数があります。指定された数値が範囲からランダムに抽出された場合、[0..10^12]の平均値はNです0.5*10^12。これは、ほとんどの場合、それ自体を検索するだけでよいことを (直感に反して) 示唆していNます。

はい、多くの場合、さらに多くの値を検索する必要があることは承知しています。

このアプローチは、比較的簡単に並列化できます。

于 2012-05-08T14:15:10.250 に答える
0

事前計算が必要な高速ソリューション:

次のルールに従って、セットをバイナリ ツリーに編成します。

  • セットの番号は葉の上にあります。
  • ツリーのルートにはr、セットの数を分割するすべての素数の最小値が含まれます。
  • 左のサブツリーは、 (無限に繰り返されないように でr除算された) の倍数のサブセットに対応します。rr
  • 右側のサブツリーは、 の倍数ではない数値のサブセットに対応しrます。

数値がセットの一部の要素を分割するかどうかをテストする場合はN、その素数分解を計算し、葉に到達するまでツリーを調べます。リーフに数値が含まれている場合はそれをN分割し、リーフが空の場合Nはセット内の要素を分割しません。

于 2012-05-08T23:09:45.773 に答える
0

質問がよくわからないので、別の質問をさせてください: 12 は [6,33,52] の約数ですか? 12 が 6、33、または 52 を割らないことは明らかです。しかし、12 の因数は 2*2*3 であり、6、33、および 52 の因数は 2*2*2*3*3*11*13 です。12 の因数はすべて集合 [6,33,52] に十分な多重度で存在するため、12 は [6,33,52] の因数であると言えます。

12 が [6,33,52] の因数ではないという場合、各数値が 12 で割り切れるかどうかをテストするよりも良い解決策はありません。単に除算を実行し、剰余を確認します。したがって、6%12=6、33%12=9、および 52%12=4 なので、12 は [6.33.52] の因数ではありません。しかし、12[6,33,52] の因数であると言う場合、数値fがセットnsの因数であるかどうかを判断するには、数値nsを順番に乗算し、各乗算の後にfを法とする剰余を取ります。残りが 0 の場合はすぐにtrueを報告し、残りが 0 にならずに数nsのリストの最後に到達した場合はfalseを報告します。

2 つの例を見てみましょう。まず、12 は [6,33,52] の因数ですか? 最初の (自明な) 乗算の結果は 6 になり、剰余は 6 になります。今度は 6*33=198 で、12 で割ると剰余が 6 になり、続行します。これで 6*52=312 と 312/12=26r0 となり、剰余は 0 になり、結果はtrueになります。次に、5 は [24,33,52] の因数ですか? 乗算チェーンは 24%5=5、(5*33)%5=2、および (2*52)%5=4 なので、5 は [24,33,52] の因数ではありません。

最近、このアルゴリズムの変種がRSA 暗号システムへの攻撃に使用されました。攻撃がどのように機能したかについては、こちらを参照してください。

于 2012-05-08T13:49:22.630 に答える
0

一般的には、O(n) 検索が最終的な結果になると思います。ただし、一般に数値がどれだけ大きいかに応じて、セットがソートされていると仮定すると(ソートされる可能性があると述べています)、Dで割り切れる数を検索して検索している場合、検索を大幅に高速化できます。現在スキャンされている x と x が D で割り切れない場合、次の候補は明らかに floor([x + D] / D) * D にあります。つまり、D = 12 でリストが

5 11 13 19 22 25 27

13 でスキャンすると、次に考えられる候補数は 24 になります。入力の分布に応じて、24 以上の最小数を検索しているため、線形検索の代わりに二分検索を使用して順方向にスキャンできます。リストで、リストがソートされます。D が大きい場合、この方法で多くの比較を保存できます。

ただし、純粋な計算の複雑さの観点から、並べ替えと検索は O(n log n) になりますが、線形スキャンだけでは O(n) になります。

于 2012-05-08T10:58:57.137 に答える