递归阶乘程序的复杂性

Question

查找数字阶乘的递归程序的复杂性是多少n？我的预感是可能的O(n).

Answer 1

如果你采用乘法O(1),那么是的,O(N)是正确的.但是请注意,乘以任意长度的两个数字x是不是 O(1)在有限的硬件-如x趋于无穷大,需要乘的时间长(例如,如果你使用Karatsuba乘法,它是O(x ** 1.585)).

理论上你可以用Schönhage-Strassen为数量足够大的数字做得更好,但我承认我没有真正的世界经验.x,"长度"或"数字位数"(在任何基础上,无论如何对N的大O来说无关紧要O(log N),当然也会增长).

如果你的意思是将你的问题限制为足够短的数字的阶乘O(1),那么就没有办法N"倾向于无穷大",因此大O符号是不合适的.

Answer 2

当您表达算法的复杂性时,它始终是输入大小的函数.只有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!然后乘以所有素因子.

Answer 3

假设你在谈论有史以来最天真的因子算法:

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

是的,该算法是线性的,在O(n)时间内运行.这种情况是因为它每次递减值时都会执行一次n,并且会递减值n直到达到0,这意味着函数会递归调用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)。