complexity-theory - 递归阶乘程序的复杂性

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的big-O都无关紧要，当然随O(log N)一起增长。

如果您打算将问题限制为足够短的阶乘以乘以O(1)，那么N不可能“趋于无穷”，因此big-O表示法是不合适的。