递归阶乘程序的复杂性

Question

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

Answer 1

如果您将乘法视为O(1)，那么是的，O(N) 是正确的。但是，请注意，在有限硬件上，将任意长度的两个数字相乘x不是O(1)——如x 趋于无穷大，乘法所需的时间会增长（例如，如果您使用 Karatsuba 乘法，则O(x ** 1.585))。

理论上，使用 Schönhage-Strassen 可以做得更好，但是我承认我对此没有任何现实经验。 x，“长度”或“位数”（无论以何种基数，对于 N 的 big-O 都无关紧要，随着 O(log N) 增长当然，

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

Answer 2

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

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

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

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

Answer 3

当您表达算法的复杂性时，它始终是输入大小的函数。仅当您相乘的数字具有固定大小时，才可以认为乘法是 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 * (总和 k = 1 到 N [k]) =
O(N^2 (log N)^2)

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

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

Answer 4

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

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)。