“给出n个整数的数组，返回其阶乘的数组。”
我不是直接遍历数组并为每个变量查找阶乘的直接方法，而是想到了一种记忆的方法，即存储先前计算的阶乘并在随后的阶乘中使用它们。
例如:7!可以计算出如果结果6则禁食得多!存储在某个地方。但是，我注意到两种算法的运行时间仍为O(n)。 (我可能是错的)这是否意味着我们没有在此处加快流程？如果是这样，这是否意味着在非树递归问题中使用备注是没有用的？ (在斐波那契，我们通过记住先前找到的值来有效地修剪递归树，在阶乘的情况下，我们实际上并没有树，更像递归阶梯)
任何意见表示赞赏。
最佳答案
但是，我注意到两种算法的运行时间仍为O(n)。
O符号在这里隐藏了最重要的特征。它仅考虑数组的长度，而不考虑数字的大小，这在处理阶乘时更为重要。
您应该使用哈希表实现备忘录。如果这样做，您将渐近地为每个条目获得O(1)。
关于recursion - 记忆化可以提高该算法的运行时间吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14787530/