Во многих алгоритмах можно заметить, что улучшения во времени часто заняты увеличением требований к памяти. Например, использование кэша позволяет ускорить вычисления, сохраняя результаты в памяти.
Существует ли теоретический предел «временного и пространственного компромисса», подобный закону Амдала, ограничивающему ускорение при распараллеливании вычислений?
Пример
Предположение : мы будем пренебрегать размером стека вызовов.
Чтобы проиллюстрировать, как работает компромисс между временем и пространством, давайте подумаем о вычислениях последовательности Фибоначчи.
Можно вычислить N-ю последовательность Фибоначчи. элемент, используя следующее уравнение:
fib(n) = fib(n-1) + fib(n-2)
fib(1) = fib(2) = 1
Обратите внимание, что для вычисления N-го элемента нам нужно вычислить 2 предыдущих. Для вычисления каждого из них нам нужно вычислить 2 предыдущих для каждого из них и так далее ...
Прямая реализация будет:
function fib(n) {
if (n == 1 || n == 2)
return 1;
return fib(n-1) + fib(n-2);
}
Давайте представим это с помощью графика для N = 6: 
Обратите внимание, что некоторые вычисления повторяются: 
Чтобы ускорить алгоритм, нужно запомнить результаты повторных вычислений и использовать их повторно. Один торгует пространством для времени .
Реализация такого компромисса:
const resultsCache = [1,1];
function fib(n) {
if (resultsCache[n])
return resultsCache[n];
fibN = fib(n-1) + fib(n-2);
resultsCache[n] = fibN;
return fibN;
}
Вопрос
Есть ли теоретический предел "компромисс между временем и пространством », как показано в примере выше? Насколько мы можем ускорить алгоритм, используя больше места?