Сохраняет ли Memoization время выполнения этого алгоритма?

Question

«Учитывая массив из n целых чисел, возвращаем массив своих факториалов».

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

Например: 7! может быть рассчитано очень быстро, если результат 6! где-то хранится. Тем не менее, я заметил, что время выполнения обоих алгоритмов по-прежнему равно O (n). (Возможно, я ошибаюсь) Это подразумевает, что мы не ускоряем процесс здесь? Если это так, означает ли это, что memoization не полезен в проблемах с недревесной рекурсией? (В Фибоначчи мы эффективно обрезаем дерево рекурсии, memoizing ранее найденные значения, в случае factorial, у нас на самом деле нет дерева, больше похоже на рекурсивную лестницу) Любые комментарии оценены.

Answer 1

Однако я заметил, что время выполнения обоих алгоритмов по-прежнему равно O (n).

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

Вы должны выполнить мемонирование с помощью хеш-таблицы. Если вы это сделаете, вы получите O (1) для каждой записи асимптотически.

Answer 2

В случае без замещения временная сложность должна быть O (n^2), так как вам понадобится (i-1) умножение для вычисления факториала (i) без воспоминаний.