我正在阅读这里投票最多的答案：Difference between Divide and Conquer Algo and Dynamic Programming，但我没有足够的声誉发表评论所以我必须发布一个新问题。
我的问题是：为什么总时间为O（n）？
根据我的理解，从大小为n的未排序数组中查找元素可能会花费时间n。
并且在找到斐波那契数的情况下，检查数字是否在备忘录中的最坏情况可能花费n倍，因此整个算法将重复n次，并且每次它将搜索该数字一次，这花费n时间。那么总时间应该是O（n ^ 2）而不是O（n）。
有人能指出我误解的地方吗？谢谢
由于记忆，渐近复杂度变为O（n）。
搜索memoized fibonacci不是O（n），考虑到你使用的数组不是LinkedList，它是O（1）。