32

数の階乗を見つけるための再帰プログラムの複雑さは何nですか？私の勘はそれがそうかもしれないということO(n)です。

4

4 に答える 4

43

掛け算をとするO(1)と、そうO(N)です、正しいです。ただし、任意の長さの2つの数値を乗算することは、有限のハードウェアでxはないことに注意してください。無限大になる傾向があるため、乗算に必要な時間が長くなります（たとえば、 カラツバ乗算を使用する場合はそうです）。O(1)xO(x ** 1.585)

理論的には、 Schönhage-Strassenを使用すると、十分に膨大な数の場合にうまくいくことができますが、実際の経験はありません。x、「長さ」または「桁数」（どのベースでも、Nのbig-Oには関係ありませんがO(log N)、もちろん、と一緒に大きくなります。

質問を、乗算するのに十分短い数の階乗に限定する場合、「無限大になりがち」O(1)という方法はないため、big-O表記は不適切です。N

于 2010-02-24T15:48:31.577 に答える
27

これまでで最も素朴な階乗アルゴリズムについて話していると仮定します。

factorial (n):
  if (n = 0) then return 1
  otherwise return n * factorial(n-1)

はい、アルゴリズムは線形であり、O（n）時間で実行されます。これは、値をデクリメントするたびに1回実行され、に達するまでn値をデクリメントするためです。つまり、関数は再帰的に呼び出されます。もちろん、これは、デクリメントと乗算の両方が定数演算であることを前提としています。n0n

もちろん、階乗を他の方法で実装する場合（たとえば、乗算の代わりに再帰的に加算を使用する場合）、はるかに時間的に複雑なアルゴリズムになってしまう可能性があります。ただし、そのようなアルゴリズムを使用することはお勧めしません。

于 2010-02-24T15:48:41.557 に答える
26

アルゴリズムの複雑さを表現するとき、それは常に入力サイズの関数としてです。O(1)乗算する数値が固定サイズである場合にのみ、乗算が演算であると想定することが有効です。たとえば、行列の積を計算するアルゴリズムの複雑さを判断したい場合は、行列の個々のコンポーネントが固定サイズであると想定できます。次に、2つの個別の行列コンポーネントの乗算がであると仮定することは有効でO(1)あり、各行列のエントリ数に従って複雑さを計算します。

ただし、計算するアルゴリズムの複雑さを把握するN!場合は、任意に大きくなる可能性があると想定する必要がNあるため、乗算が演算であると想定することはできませんO(1)。

nビットの数値にmビットの数値を掛けたい場合、単純なアルゴリズム（手作業で行う種類）には時間O(mn)がかかりますが、より高速なアルゴリズムがあります。

コンピューティングのための簡単なアルゴリズムの複雑さを分析したい場合N!

    factorial(N)
       f=1
       for i = 2 to N
          f=f*i

       return f

次に、forループのk番目のステップで、を乗算(k-1)!しkます。表現に使用されるビット数(k-1)!はO(k log k)であり、表現に使用されるビット数kはですO(log k)。したがって、乗算(k-1)!に必要な時間kはO(k (log k)^2)（単純な乗算アルゴリズムを使用すると仮定して）です。次に、アルゴリズムにかかる合計時間は、各ステップでかかる時間の合計です。

sum k = 1 to N [k (log k)^2] <= (log N)^2 * (sum k = 1 to N [k]) =
O(N^2 (log N)^2)

O(n*log(n)*log(log(n)))2 nビットの数値に時間がかかるSchönhage-Strassenのような、より高速な乗算アルゴリズムを使用することで、このパフォーマンスを向上させることができます。

パフォーマンスを向上させるもう1つの方法は、より優れたアルゴリズムを使用してを計算することN!です。私が知っている最速のものは、最初にの素因数分解を計算し、N!次にすべての素因数を乗算します。

于 2011-06-01T02:37:59.277 に答える
8

再帰的階乗の時間計算量は次のようになります。

factorial (n) {    
    if (n = 0) 
        return 1
    else
        return n * factorial(n-1)
}

それで、

1回の再帰呼び出しの時間計算量は次のようになります。

T(n) = T(n-1) + 3   (3 is for As we have to do three constant operations like 
                 multiplication,subtraction and checking the value of n in each recursive 
                 call)

     = T(n-2) + 6  (Second recursive call)
     = T(n-3) + 9  (Third recursive call)
     .
     .
     .
     .
     = T(n-k) + 3k
     till, k = n

     Then,

     = T(n-n) + 3n
     = T(0) + 3n
     = 1 + 3n

Big-Oh表記で表すには、

T（N）はnに正比例します。

したがって、再帰階乗の時間計算量はO（n）です。再帰呼び出し中に余分なスペースが必要ないため、スペースの複雑さはO（N）です。

于 2018-07-22T13:51:39.960 に答える