1

下面的算法（伪代码）的时间复杂度是多少？我很难分析它。它是在另一个线程中指定的问题的实现：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，方向定义为 DOWN=0, LEFT=1, RIGHT=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
4

1 回答 1

1

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

如果我们让 G=(V,E) 是一个图，其中 V={maxPath(i, j, p, d) : 对于所有可能的 i, j, p 和 d } 并且 E= {uv : u = f(i , j, p, d) 和 v = f(i', j', p', d') }。我们知道 G 是一个状态图，显然是 DAG（有向无环图）。然后，我们可以使用 memoization 计算 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)。

于 2012-10-15T10:47:15.123 回答