Запоминание и табулирование
Давайте рассмотрим оба метода, поставив каждый из них перед одной и той же проблемой: как найти конкретное число Фибоначчи?
Мемоизация
Во-первых, давайте воспользуемся рекурсией для решения этого вопроса.
Ex :
Для каждой итерации
Функция fib( ){
Пример: fib 4
===> Найдите два предыдущих тома.
Fib 3 fib 2
Результат возвращается в fib(0) или fib(1)
//0 или 1
}
Время выполнения этой рекурсии будет экспоненциальным, с O (2 ^ n)
Это возможность представить концепцию мемоизации.
Он заключается в хранении результатов, возвращаемых функцией, для ускорения будущих операций.
Ведь в разных случаях это позволит нам избежать выполнения затратных функций, собирая нужные значения за постоянное время.
В этом случае: белый вычисляет результат fib (3) один раз, нам не нужно будет пересчитывать его снова во время следующих итераций.
Это позволяет резко сократить время поиска.
Действительно, без мемоизации O(2^n)
С запоминанием: O(n)
На самом деле дерево просматривается только один раз, а не для каждой операции.
Мемоизация следует «нисходящему подходу». Действительно , мы начинаем с вершины дерева, к каждому дочернему узлу, чтобы добраться до конечного узла.
Метод табуляции
Теперь давайте проверим метод табулирования :
Этот метод использует итерацию вместо рекурсии.
Действительно, нам просто нужно начать с добавления 0 к индексу 0 и 1 к индексу 1.
Затем, используя индекс, в каждом блоке памяти просто вычислить добавление двух последних блоков. Это позволяет прийти к значению n.
В отличие от мемоизации, смысл в том, чтобы следовать восходящему подходу.
Действительно, мы начинаем с 0 или 1, чтобы прийти к значению n.
Для решения такой проблемы доступны как рекурсивный, так и итеративный подходы.
