0

入力が単なる数値で、出力が除数のセットであるアルゴリズムがある場合、入力は常に1つの数値になり、アルゴリズムの反復回数は数値の大きさによって異なります。そのようなアルゴリズムの大きな表記法は? アルゴリズム：

1: Set m := 2.
2: Set S := {} for S a multi-set.
3: while m  <= n^0.5
do
4: if m divides N then
5: Set S U m
6: else
7: Set m = m + 1.
 8: end if
 9: end while
 10: Return the set S of divisors found.
4

1 に答える 1

1

漸近的複雑度を表す big-O 表記の変数を入力数値自体にするか、その数値を表すのに必要なビット数にすることができます。これらの 2 つの規則は、劇的に異なる漸近分類を生じさせるため、結果を報告する際にどちらを使用するかを明確にすることが重要です。

一般に、数値が大きすぎて bignum が必要な場合について話すときは、ビット数の規則を使用する傾向があり、入力が のサイズによって制限されている場合は、数値の意味の規則を使用する傾向があります。機械語。しかし、それは、特定の状況で自分自身で確認する必要がある最初の推測を取得する以外に、信頼できるものではありません.

選択は、算術演算に使用しているコスト モデルと密接に関連する傾向があります。ビットをカウントする場合、n ビット値の算術演算には O(n) 時間がかかると想定するのが一般的ですが、入力数値の意味を扱う場合は、通常、数値の算術演算が一定時間で行われると想定します。

あなたの場合、 O(2^n) または O(sqrt(m)) のようなものが得られます。ここで、n は入力のビット数で、m は入力自体です。(詳細は、マルチセット プリミティブの実行方法によって異なります)。

疑似多項式時間も参照してください。

于 2012-11-09T00:32:00.247 に答える