Существует ли какой-либо общий теоретический предел для временного и пространственного компромисса? - PullRequest
Новая
       33

Существует ли какой-либо общий теоретический предел для временного и пространственного компромисса?

1 голос
/ 17 октября 2019

Во многих алгоритмах можно заметить, что улучшения во времени часто заняты увеличением требований к памяти. Например, использование кэша позволяет ускорить вычисления, сохраняя результаты в памяти.

Существует ли теоретический предел «временного и пространственного компромисса», подобный закону Амдала, ограничивающему ускорение при распараллеливании вычислений?

Пример

Предположение : мы будем пренебрегать размером стека вызовов.
Чтобы проиллюстрировать, как работает компромисс между временем и пространством, давайте подумаем о вычислениях последовательности Фибоначчи.
Можно вычислить 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: enter image description here Обратите внимание, что некоторые вычисления повторяются: Repeated elements Чтобы ускорить алгоритм, нужно запомнить результаты повторных вычислений и использовать их повторно. Один торгует пространством для времени .

Реализация такого компромисса: 

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;
}

Вопрос

Есть ли теоретический предел "компромисс между временем и пространством », как показано в примере выше? Насколько мы можем ускорить алгоритм, используя больше места?

...