递归阶乘程序的复杂性 [英] Complexity of recursive factorial program

问题描述

查找数字 n 的阶乘的递归程序的复杂性是什么？我的直觉是它可能是 O（n）。

解决方案

如果将乘法作为 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 不可能趋于无穷大，因此big-O表示法是不合适的。 / p>

What's the complexity of a recursive program to find factorial of a number n? My hunch is that it might be O(n).

解决方案

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

You can theoretically do better for sufficiently huge numbers with Schönhage-Strassen, but I confess I have no real world experience with that one. x, the "length" or "number of digits" (in whatever base, doesn't matter for big-O anyway of N, grows with O(log N), of course.

If you mean to limit your question to factorials of numbers short enough to be multiplied in O(1), then there's no way N can "tend to infinity" and therefore big-O notation is inappropriate.

这篇关于递归阶乘程序的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！