带缓存的递归求解最长回文子序列的大O分析

Question

我不擅长算法分析。源代码来自这个地方：https://repl.it/KREy/4

这段代码不是动态规划，而是使用缓存通过牺牲内存来优化 BigO。但是，我就是不知道加了这个缓存机制之后，如何从数学上计算BigO。有哪位高手给个解释吗？

为了方便阅读，我将把它们复制粘贴到下面space：

// using cache to optimize the solution 1 from http://www.techiedelight.com/longest-palindromic-subsequence-using-dynamic-programming/


const cache = {};

var runningtime = 0;
var runningtimeWithCache = 0;


function computeGetLP(x, start, end){

  const answer = a => {
    runningtime++;
    return a;
  }

  console.log("try to compute: " + x + " " + start + " " + end + " ");


  if(start > end)
    return answer(0);

  if(start == end)
    return answer(1);

  if(x[start] == x[end])
    return answer(2 + computeGetLP(x, start+1, end-1));

  return answer(Math.max(computeGetLP(x, start+1, end),
                  computeGetLP(x, start, end-1)));
}

function computeGetLPWithCache(x, start, end){

  const answer = a => {
    runningtimeWithCache ++;
    console.log("do cache: " + x + " " + start + " " + end + " is " + a);
    cache["" + x + start + end] = a;
    return a;
  }

  console.log("try to compute: " + x + " " + start + " " + end + " ");

  if(cache["" + x + start + end]){
    console.log("hit cache " + x + " " + start + " " + end + " "+ ": ",cache["" + x + start + end]);
    return cache["" + x + start + end];    
  }

  if(start > end)
    return answer(0);

  if(start == end)
    return answer(1);

  if(x[start] == x[end])
    return answer(2 + computeGetLPWithCache(x, start+1, end-1));

  return answer(Math.max(computeGetLPWithCache(x, start+1, end),
                  computeGetLPWithCache(x, start, end-1)));
}

const findLongestPadlindrom1 = s => computeGetLPWithCache(s, 0, s.length-1)
const findLongestPadlindrom2 = s => computeGetLP(s, 0, s.length-1)

const log = (function(){
  var lg = [];
  var output = function(text){
    lg.push(text);
  }
  output.getRecord = function(){
    return lg;
  }
  return output;
})();

log("Now let's do it with cache")
log("result: "+findLongestPadlindrom1("ABBDCACB"))
log("running time is: " + runningtimeWithCache)

log("Now let's do it without cache")
log("result: "+findLongestPadlindrom2("ABBDCACB"))
log("running time is: " + runningtime)

log.getRecord();

Answer 1

我也不是算法专家，但我记得算法导论第 15 章中的缓存技术，就在动态规划旁边。它对 DP 具有相同的大 O，在您的情况下为 O(n^2)。

每次调用 computeGetLPWithCache() 的成本为 O(1)，因为它不包含循环。考虑每次递归中 x[start] != x[end] 的最坏情况。我们要调用多少次 computeGetLPWithCache()？

设n = length(x)，[start, end]表示调用computeGetLPWithCache(x, start, end)，F(n)等于调用次数。在 computeGetLPWithCache(x, 0, n) 中，发出了 2 个子调用 - [0, n-1] 和 [1, n]。前者花费 F(n)，当我们做后者时，我们发现在每次迭代中，第一次调用的 [start, end] 范围是 [0, n-1] 的真实子集，其结果已经写入在 [0, n-1] 调用期间缓存，因此不需要递归。只需要计算其中包含元素 n 的第二次调用；有 n 个这样的调用 [1,n][2,n][3,n]...[n,n]（每个堆栈层一个），所以 F(n+1) = F(n) + O(n).

F(n) = F(n-1) + O(n-1) = F(n-2) + O(n-2) + O(n-1) = ... = O (1+2+...+(n-1)) = O(n^2).

希望我已经理解了意思。欢迎回复。

带缓存的递归求解最长回文子序列的大O分析

Big O analysis of solving longest palindromic subsequence by recursion with cache

javascript

algorithm

big-o

caching

palindrome