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

Question

"Given an array of n integers, return an array of their factorials."

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

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

Answer 1

However, I noticed the run time of both algorithms is still O(n).

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

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