递归算法的复杂性

我有一个算法，我想找出它的复杂性，但有递归，我不知道如何计算递归。我的代码是：递归算法的复杂性

public boolean algorithm(int x, int y) { 
    if (x == matrixHeight - 1 && matrix1[x][y] == '0') { 
     return true; 
    } else if (x == 1 && matrix1[x-1][y] == '0') { 
     return true; 
    } else if (y == matrixWidth - 1 && matrix2[x][y] == '0') { 
     return true; 
    } else if (y == 1 && matrix2[x][y-1] == '0') { 
     return true; 
    } 
    if (matrix1[x-1][y] == '0' && tempMatrix[x-1][y] == '-'){ 
     path.push(new int[]{x-1, y}); 
     tempMatrix[x-1][y] = '+' 
     if (!algorithm(x-1, y)) { 
      path.pop(); 
     } else { 
      return true; 
     } 
    } 
    if (matrix2[x][y] == '0' && tempMatrix[x][y+1] == '-'){ 
     path.push(new int[]{x, y+1}); 
     tempMatrix[x][y+1] = '+'; 
     if (!algorithm(x, y+1)) { 
      path.pop(); 
     } else { 
      return true; 
     } 
    } 
    if (matrix1[x][y] == '0' && tempMatrix[x+1][y] == '-'){ 
     path.push(new int[]{x+1, y}); 
     tempMatrix[x+1][y] = '+'; 
     if (!algorithm(x+1, y)) { 
      path.pop(); 
     } else { 
      return true; 
     } 
    } 
    if (matrix2[x][y-1] == '0' && tempMatrix[x][y-1] == '-'){ 
     path.push(new int[]{x, y-1}); 
     tempMatrix[x][y-1] = '+'; 
     if (!algorithm(x, y-1)) { 
      path.pop(); 
     } else { 
      return true; 
     } 
    } 
    return false; 
}

在那里，x，y在矩阵坐标。
matrix1和matrix2是包含'0'或'1'
tempMatrix二维阵列由包含 '+' 或二维阵列 ' - '
path是堆栈
matrixHeight是matrix1.length
matrixWidth是matrix[0].length
N,M是矩阵的大小（constan t）

注意：这是使用回溯的迷宫解算器。

来源

2011-04-21 Martynas

此代码需要注释。 – Brad 2011-04-21 19:41:46

如果您可以简要说明此代码的作用以及如何执行此操作，那将会很有帮助。 – MAK 2011-04-21 19:57:03

此代码不需要注释，它只需要有意义的名称。 – 2011-04-21 23:52:57

它看起来像一个深度第一迷宫解算器，如果您可以退出迷宫，则返回true，否则返回false。复杂性是O(lines * columns)，因为在最坏的情况下你访问每个单元的次数是固定的。

从（1,1）开始。你的算法会上升，回溯，向右，再试一次，回溯，再次右回溯，然后下降等等。对于像这样构建的迷宫，它看起来像你的算法将花费大量的时间来解决它们。

事实上，大多数递归（深度优先更准确）方法将花费很长的时间，因为它永远是有可能迫使他们做的步骤的最大数量。

查看Lee algorithm以获得更好的方法。

来源

2011-04-21 19:57:25 IVlad

是的你是对的。这是带回溯的Maze算法。迷宫为空时，复杂度为O（行*列）。如果迷宫占据特定数量的墙壁，那么复杂程度如何？ – Martynas 2011-04-21 20:29:27

@Martynas - 不，如果迷宫空了，那是你最好的情况。在这种情况下，这是'O（n）'。对于特定数量的墙壁，我不确定是否容易分辨，如果您知道的话，它也不会帮助您。你应该假设它是'O（lines * columns）'。 – IVlad 2011-04-21 20:38:57

对于递归，您需要生成一个递归关系并求解。请参阅http://en.wikipedia.org/wiki/Recurrence_relation。没有一种方法可以解决每一个复发关系，甚至从算法中产生一个复发关系。

一个例子是合并排序。考虑每次递归调用完成多少工作。首先，有一个恒定的时间划分;然后进行两次递归调用;那么线性时间合并。递归调用需要多少工作？那么，每个人都做同样的事情，两个递归调用加线性合并步骤。所以你需要表达树的深度和宽度。您知道输入大小为n时，树的高度为O（log（n）），并且在每一步都完成了O（n）合并工作，因此O（n log（n））的工作是总计完成。

来源

2011-04-21 19:35:07

实际上这个算法的复杂性真的很简单。

到algorithm每次调用使得零至四个递归调用algorithm和做其他工作一定一定量。所以，如果我们能约束的是algorithm被称为次数那么我们就知道了复杂性。现在，请注意，在之前，每调用algorithm（除第一个外），您将tempMatrix的元素从' - '更改为'+'。因此，调用算法的次数受tempMatrix大小限制，复杂度为O(matrixWidth * matrixHeight)。

另一种方法（对于更多有意义的变量名会更明显）只是注意到您正在x-y网格上进行深度优先搜索。所以每个“方”都会被访问一次。

来源

2011-04-22 00:00:16

递归算法的复杂性

回答

相关问题