复杂递归阶乘程序的

Question

什么是一个递归程序，找了一些n的阶乘的复杂性？我的直觉是它可能是O(n)。

Answer 1

如果你把乘法为O(1)，那么，O(N)是正确的。但是请注意，乘以任意长度x的两个数字是不O(1)有限硬件 - 如x趋于无穷大，需要乘的时间长（例如，如果你使用Karatsuba multiplication，这是O(x ** 1.585)）。

理论上可以做足够庞大的数字与Schönhage-Strassen更好，但我承认我有一个没有任何现实世界的经验。 x，“长度”或“数字位数”（无论在什么基础上，对于N的大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）的时间：T他是这样的，因为它每次递减值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乘以(k-1)!。用于表示(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对于2位n位数需要时间O(n*log(n)*log(log(n)))。

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