Как сложность уменьшается до O(n^2) от O(2^n) в случае запоминания?
В настоящее время я изучаю динамическое программирование с помощью техники запоминания и табулирования. Со ссылкой на следующую ссылку (самая большая проблема с возрастающей последовательностью) я не понял, как сложность уменьшается до O(n^2) с O(2^n), когда мы запоминаем?
https://leetcode.com/problems/longest-increasing-subsequence/solution/
2 ответа
Когда вы запоминаете функцию, вы делаете заметку каждый раз, когда вызываете эту функцию: а) параметров и б) результата. Затем, когда вы захотите снова вызвать функцию, вы отметите в своих заметках, вызывали ли вы эту функцию раньше, с параметрами, которые вы хотите использовать в этот раз. Если у вас есть, вам не нужно снова вызывать функцию, потому что у вас уже есть результат. Таким образом, функция вызывается только столько раз, сколько у вас есть различных параметров: если вы хотите вызвать ее с параметрами, которые вы уже использовали, вам не нужно вызывать ее.
Этот подход хорошо работает, когда а) функция является детерминированной, то есть возвращает одно и то же значение каждый раз, когда она вызывается с одинаковыми параметрами, и б) функция является дорогой по сравнению со стоимостью запоминания.
Пример, который вы приводите, говорит так:
В предыдущем подходе многие рекурсивные вызовы приходилось делать снова и снова с одинаковыми параметрами. Эту избыточность можно устранить, сохранив результаты, полученные для конкретного вызова, в двумерном массиве запоминания.
Здесь рассматриваемая функция называется O (2n) раз, но только с O (n2) различными наборами параметров. Используя запоминание, функция вызывается только один раз для каждого отдельного набора параметров (O (n2)), а не каждый раз, когда алгоритму требуется ответ (O (2n)).
Я думаю, что ответ дается по ссылке, предоставленной вами только в вопросе! Я процитирую это оттуда как есть:
"для конкретного вызова в двумерном массиве запоминания memomemo. memo[i][j]memo[i][j] представляет возможную длину LIS, используя nums [i] nums [i] в качестве предыдущего элемента, рассматриваемого как быть включенным / не включенным в LIS, причем nums[j]nums[j] является текущим элементом, который считается включенным / не включенным в LIS."
Я предполагаю, что вы поняли первое решение рекурсии, а затем перешли к этому решению, поэтому к настоящему времени вы бы поняли основную концепцию того, что мы пытались сделать в этом первом решении: мы проверяли, получаем ли мы максимум, включив или исключая текущий элемент массива. Вот почему мы делали 2 вызова каждый раз, один принимая текущий элемент как предысторию, а другой сохраняя предыдение как есть (разумеется, мы также соответствующим образом принимали другие параметры функции!). Благодаря такому подходу он брал O(2^n).
так что если мой prev = n-2 и cur = n-1, то я могу либо исключить n-1, либо рассмотреть n-1 при подсчете LIS. наши вызовы функций будут выглядеть примерно так:
prev=n-2,cur=n-1
prev=n-1, cur=n prev=n-2, cur = n
prev=n-1, cur=n+1 prev=n, cur=n+1 prev=n-2,cur=n+1 prev=n,cur=n+1
Таким образом, ясно, что мы будем без необходимости вызывать функцию с prev = n и cur = n+1 дважды, и все вызовы потомков также будут вызываться дважды! Таким образом, ключевая идея здесь - использовать запомненный ответ напрямую и тем самым исключить все вызовы функций потомков.
другой пример с массивом = [1, 2, 3, 4]
min_int, 1
min_int, 2 1, 2
min_int,3 2, 3 1, 3 2, 3
min_int, 4 3, 4 2, 4 3, 4 1, 4 3, 4 2, 4 3, 4
здесь вызов 2,3 выполняется дважды, этот пример не очень эффективен, поскольку размер массива мал, но я надеюсь, что вы поняли, что мы уменьшаем сложность в геометрической прогрессии, поскольку мы исключаем последующие вызовы функций.
Так сколько звонков может быть? приблизительно, мы можем думать об ответе как: каждый элемент может присутствовать при prev и текущем параметре, так что может быть приблизительно O(n^2) возможностей, и мы их переоценивали!