algorithm - 利用内存分析 NxN 矩阵中最重路径的时间复杂度

Question

下面算法(伪代码)的时间复杂度是多少？我很难分析它。它是另一个线程中指定问题的实现:Algorithm to find max cost path of length N in matrix, from [0,0] to last row .但是因为我是新来的，所以我没有足够的分数在线程中发表评论(我认为)？这是我的第一篇文章，如果我做错了什么，请原谅。

该算法使用带有 cache[][][][] 的内存。在初始化期间，cache[][][][] 被填充为 -1。

该方法使用 maxPath(0,0,m,DOWN) 调用。其中 m 是要走的步数，n<=m<=n^2，方向定义为向下=0、向左=1、向右=2。

function maxPath(i, j, fuel, direction)
    if i = n OR j = n OR j < 0 OR fuel = 0 then
         return 0;
    end if
    if cache[i][j][f-1][d] != -1 then
         return cache[i][j][f - 1][d];
    end if
    ret := 0
    acc+ = matrix[i][j]
    ret:=max(ret,maxPath(i+1, j, fuel-1, DOWN))
    if f > n - i then . If there is enough steps to move horizontally
        if d = RIGHT or d = DOWN then
            ret:=max(ret,maxPath(i, j+1, fuel-1, RIGHT))
        end if
        if d = LEFT or d = DOWN then
            ret:=max(ret,maxPath(i, j-1, fuel-1, LEFT))
        end if
    end if
    return cache[i,j,fuel-1,direction] = ret + matrix[i][j]
end function

Answer 1

好的，我已经解决了，我想我应该分享我的结果。

如果我们让 G=(V,E) 是一个图，其中 V={maxPath(i, j, p, d) : for all possible i, j, p and d } and E= {uv : u = f(i, j, p, d) 和 v = f(i', j', p', d') }。我们有 G 是一个状态图，它显然是 DAG(有向无环图)。然后，我们可以使用内存计算 maxPath。

我们有

    n possible values for i
    n possible values for j
    m possible values for fuel (which in worst case is n^2)
    3 possible values for direction

然后我们有 n * n * m * 3 个不同的 maxPath 函数被调用，在最坏的情况下是 n^4*3。所以，我们有 O(n^4) 个不同的函数。每次函数调用都在 O(1) 时间内运行。因为该图具有次优结构，所以每个子问题都是原始问题的问题。因此，通过内存，我们不必两次计算相同的“函数”，因此我们得到 O(n^4)。