algorithm - 如果递归函数的输入大小减少 2，它是阶乘时间算法吗？

Question

我有一个递归定义如下:

f(input_array) = {f(input_array - i) for i in input_array, if len(input_array) > 1; 0, else}

我知道这是一个阶乘解，因为每次迭代输入的大小都会减少 1。

输入的大小如下所示:
n
n-1个
n-2个
n-3
...
n-(n-1)


这显然是一个阶乘时间解决方案。我想知道输入大小减少 2 会发生什么。这也是阶乘吗？

Answer 1

时间复杂度为n⋅(n-2)⋅(n-4)⋅...⋅2。

当n为偶数时，可以改写如下:

[2⋅(n/2)] ⋅ [2⋅(n/2 - 1)] ⋅ [2⋅(n/2 - 2)] ⋅ ... ⋅ (2⋅1) = 2^n/2 ⋅ (n/2)!

---

有趣的是，有一个术语表示相差 2 的因子的初始乘积，双阶乘，它使用 n!! 表示法(感谢 Ari Hietanen 用于在评论中指出它)——请参阅 wolfram 上的这些链接或 wikipedia获取此表达式的其他属性。