0

再帰的アルゴリズムの分析を理解するために助けが必要です。私はすぐにこのアルゴリズムを作り上げました、そして複雑さが何であるか知りたいです：

int FunctionExampple( A1, A2, ... An )
{
    product = 1;
    if( n == 2)
    {
        product = multi(A1, A2);
    }
    else 
    {
        product = multi(A1, FunctionExample( A2, A3, ..., An ) );
   }
   return product; 
}

ここで、関数multiにO（n ^ 1.59）時間がかかると仮定すると、複雑さはどのようになりますか？それはO（n ^ 1.59）のままですか、それとも再帰呼び出しは再帰呼び出しの数を説明するためにO（n ^ 1.59 * n）にしますか？みんなありがとう。

PS：私はこれをすぐに書き上げました、そして構文とそのすべてのものは重要ではありません。

4

1 に答える 1

1

O（n 1.59）のパラメータ'n'は、引数の数ではなく、'multi'への引数のサイズを測定します。したがって、重要なのは、「multi」からの出力のサイズがその入力のサイズにどのように関連するかです。たとえば、「multi」の結果が引数のいずれかのサイズの2倍である場合、A、B、Cのサイズがnであるmulti（A、multi（B、C））の呼び出しはO（n 1.59 +（2n ）1.59）、そしてこの方法で複数の呼び出しをマルチにチェーンすると、指数関数的に成長します。一方、'multi'が入力と同じサイズの値を返す場合、O（kn 1.59）が得られます。ここで、kはFunctionExampleの引数の数であり、nはそれらの（最大の）サイズです。

したがって、「multi」の動作によって異なります。たとえば、有限体内での乗算と乗算の場合は大きな違いがあります。後者の場合、結果は入力から大きくなりませんが、無制限の整数の場合、結果のサイズは大きくなります。

于 2012-06-05T18:23:35.750 に答える