13

私は計算の複雑さ、BigOh 記法などの研究を始めており、整数因数分解アルゴリズムを実行してその複雑さを判断する任務を負っていました。アルゴリズムを作成して動作していますが、複雑さの計算に問題があります。擬似コードは次のとおりです。

DEF fact (INT n)
BEGIN
    INT i

    FOR (i -> 2 TO i <= n / i STEP 1)
    DO
        WHILE ((n MOD i) = 0)
        DO
            PRINT("%int X", i)
            n -> n / i
        DONE
    DONE

    IF (n > 1)
    THEN
        PRINT("%int", n)

END

私がやろうとしたことは、非常に間違っていると思います。

f(x) = n-1 + n-1 + 1 + 1 = 2n

それで

f(n) = O(n)

因数分解アルゴリズムは計算が難しいと考えられており、多項式にすることさえできないため、これは間違っていると思います。それで、あなたは私を助けるために何を提案しますか? 多分私は夜のこの時間に疲れすぎて、これをすべて台無しにしています:(

前もって感謝します。

4

3 に答える 3

28

この現象は疑似多項式と呼ばれます: 多項式のように見えますが、実際には多項式ではない複雑さです。特定の複雑さ (ここではn ) が多項式かどうかを尋ねる場合、複雑さが入力のサイズにどのように関係しているかを調べる必要があります。並べ替え (たとえば、マージ並べ替えはO(n lg n)で解決できます) などのほとんどの場合、nは入力のサイズ (要素の数) を表します。ただし、この場合、nは入力のサイズを表していません。入力値です。では、nの大きさは? 自然な選択はnのビット数で、これはおよそlg nです. w = lg nをnのサイズとします。O (n) = O(2^(lg n)) = O(2^w) - つまり、入力サイズwの指数関数です。

( O(n) = O(2^(lg n)) = O(2^w)は常に真であることに注意してください。問題は、入力サイズがnまたはw = lg nで記述されるかどうかです。また、nの場合はリスト内の要素の数を表しますが、厳密に言えば、入力の合計サイズを取得するには、リスト内のすべての要素のビット数をカウントする必要があります; ただし、通常、リストでは、すべての数値のサイズが制限されていると想定します (たとえば、 32ビット)))。

于 2011-05-15T01:30:48.013 に答える
0

big-O表記でnは、は入力のサイズであり、入力自体ではありません（あなたの場合のように）。入力のサイズはlg(n)ビットです。つまり、基本的にあなたのアルゴリズムは指数関数的です。

于 2011-05-15T05:39:59.053 に答える
0

アルゴリズムが再帰的であるという事実を使用してください。f(x) が因数分解に必要な演算の数である場合、n が見つかった最初の因数である場合、f(x)=(n-1)+f(x/n) になります。因数分解アルゴリズムの最悪のケースは、アルゴリズムの複雑さが O(n) である素数です。

因数分解アルゴリズムが「難しい」のは、主にそれらが非常に大きな数で使用されるためです。

于 2011-05-15T02:33:05.847 に答える