32

递归程序找到一个数字的阶乘的复杂性是多少n？我的预感是它可能是O(n)。

4

4 回答 4

43

If you take multiplication as O(1), then yes, O(N) is correct. However, note that multiplying two numbers of arbitrary length x is not O(1) on finite hardware -- as x tends to infinity, the time needed for multiplication grows (e.g. if you use Karatsuba multiplication, it's O(x ** 1.585)).

从理论上讲，您可以使用Schönhage-Strassen为足够大的数字做得更好，但我承认我没有真实世界的经验。x，“长度”或“位数”（在任何基础上，对于 N 的 big-O 都无关紧要，O(log N)当然随着 增长。

如果您的意思是将您的问题限制在足够短的数字的阶乘上O(1)，那么就N不可能“趋于无穷大”，因此大 O 表示法是不合适的。

于 2010-02-24T15:48:31.577 回答
27

假设您正在谈论有史以来最天真的阶乘算法：

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

是的，该算法是线性的，在 O(n) 时间内运行。之所以如此，是因为它每次递减 value 时都会执行一次n，并且会递减 valuen直到达到0，这意味着该函数被递归调用n多次。当然，这是假设减法和乘法都是常数运算。

当然，如果您以其他方式实现阶乘（例如，递归地使用加法而不是乘法），您最终会得到一个时间复杂得多的算法。不过，我不建议使用这样的算法。

于 2010-02-24T15:48:41.557 回答
26

当您表达算法的复杂性时，它始终是输入大小的函数。O(1)如果您要相乘的数字是固定大小的，那么假设乘法是一个操作才是有效的。例如，如果您想确定计算矩阵乘积的算法的复杂性，您可能会假设矩阵的各个分量是固定大小的。那么假设两个单独的矩阵分量相乘是有效的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)

您可以通过使用更快的乘法算法来提高此性能，例如 Schönhage-Strassen，它需要时间O(n*log(n)*log(log(n)))来处理 2 个 n 位数字。

提高性能的另一种方法是使用更好的算法来计算N!. 我所知道的最快的首先计算素因子分解，N!然后将所有素因子相乘。

于 2011-06-01T02:37:59.277 回答
8

递归阶乘的时间复杂度为：

factorial (n) {    
    if (n = 0) 
        return 1
    else
        return n * factorial(n-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 回答