Я читал ответ, получивший наибольшее количество голосов: Разница между алгоритмом "разделяй и властвуй" и динамическим программированием ,
но у меня недостаточно репутации, чтобы комментировать, поэтому я должен опубликовать новый вопрос.
Мой вопрос: почему общее время O (n)?
Насколько я понимаю, поиск элемента из несортированного массива размера n может стоить времени n.
А в случае нахождения числа Фибоначчи наихудший случай проверки того, находится ли число в памятке, может стоить n времени, поэтому весь алгоритм будет повторяться n раз, и каждый раз он будет искать число один раз, который стоит n раз. Тогда общее время должно быть O (n ^ 2) вместо O (n).
Кто-нибудь может указать, где я неправильно понял? Спасибо