Влияние скорости выполнения на используемое пространство памяти

До сих пор мы обсуждали только временную сложность, но та же проблема (и те же классы сложности) существует и для потребления памяти. Почему бы не обменять одно на другое?

Один из способов использовать это называется memorization.

Идея меморизации заключается в следующем: если функция повторно вызывается для одних и тех же входных данных, которые трудно вычислить, сохраняйте результаты в памяти и повторно используйте их вместо повторного вычисления одного и того же снова и снова.

Например, вычисление факториала n требует n умножения.

Эта функция-оболочка сохраняет все результаты на карте, и, если заданное значение n уже было вычислено, она возвращает результат из карты; а в противном случае звонит fac(n).

Пришло время поработать с кодом!

Запоминаемая функция начинается с той же временной сложности, что и исходная функция факториала. Однако со временем для большинства вызовов facm() требуется только один доступ к карте. И, хотя спецификация языка Go не дает никаких гарантий производительности для доступа к карте, мы можем с уверенностью предположить, что это лучше, чем O(2^n).