recursion - 记忆化是否提高了该算法的运行时间？

Question

“给定一个包含 n 个整数的数组，返回它们的阶乘数组。”

我没有直接遍历数组并为每个数组查找阶乘，而是考虑了一种记忆化方法，在该方法中我存储先前计算的阶乘并在后续的阶乘中使用它们。

例如：7！如果结果 6 可以计算多禁食！存储在某处。但是，我注意到两种算法的运行时间仍然是 O(n)。（我可能错了）这是否意味着我们没有在这里加快进程？如果是这样，这是否意味着记忆化在非树递归问题中没有用？（在斐波那契中，我们通过记忆先前找到的值来有效地修剪递归树，在阶乘的情况下，我们并没有真正的树，更像是一个递归阶梯）任何评论表示赞赏。

Answer 1

在没有记忆的情况下，时间复杂度应该是 O(n^2) 因为你需要 (i-1) 乘法来计算没有记忆的阶乘(i)。

Answer 2

但是，我注意到两种算法的运行时间仍然是 O(n)。

O-Notation 隐藏了这里最重要的特征。它只考虑数组的长度而不考虑数字的大小，这在处理阶乘时要重要得多。

您应该使用哈希表实现记忆。如果你这样做，那么你将渐近地得到每个条目的 O(1)。