时间戳

首页 > 解决方案 > 网格中的机器人大 O 解释

java - 网格中的机器人大 O 解释

问题描述

我已经对这个问题进行了一些研究，但我找不到任何解释它的时间复杂度。

在破解编码面试第6版时有一个问题：

网格中的机器人：想象一个机器人坐在网格的左上角，有 r 行和 c 列。机器人只能在两个方向上移动，向右和向下，但某些单元格是“禁区”，因此机器人无法踩到它们。设计一个算法来寻找机器人从左上角到右下角的路径

这是作者的解决方案，她解释说这个问题有 O(2^(r+c)) & 使用记忆成本 O(r*c) （其中 r 是行数，c 是列数）

“这个解决方案是 O(2^(r+c))，因为每条路径都有 r+c 步，我们可以在每一步做出两个选择”

ArrayList<Point> getPath(boolean[][] maze) {
2 if (maze == null || maze.length == 0) return null;
3 ArrayList<Point> path = new ArrayList<Point>()j
4 if (getPath(maze, maze.length - 1, maze[0].length - 1, path)) {
5 return path;
6 }
7 return null;
8 }
9
10 boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path) {
11 / * If out of bounds or not available, return. */
12 if (col < 0 || row < 0 || !maze[row][col]) {
13 return false;
14 }
15
16 boolean isAtOrigin = (row == 0) && (col == 0);
17
18 /* If there's a path from the start to here, add my location. */
19 if (isAtOrigin || getPath(maze, row, col - 1, path) ||
2B getPath(maze, row - 1, col, path)) {
21 Point p = new Point(row, col);
22 path.add(p);
23 return true;
24 }
25
26 return false;
27 }

当添加一个 hashmap 来缓存之前调用的失败点时，为什么它只花费 O(r*c) ？

boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path,
12 HashSet<Point> failedPoints) {
13 /* If out of bounds or not available, return. */
14 if (col < 0 || row < 0 || !maze[row][col]) {
15 return false;
16 }
17
18 Point p = new Point(row, col);
19
20 /* If we've already visited this cell, return. */
21 if (failedPoints.contains(p)) {
22 return false;
23 }
24
25 boolean isAtOrigin = (row == 0) && (col == 0);
26
27 /* If there's a path from start to my current location, add my location. */
28 if (isAtOrigin || getpath(maze, row, col - 1, path, failedPoints) ||
29 getPath(maze, row - 1, col, path, failedPoints) {
30 path.add(p);
31 return true;
32 }
33
34 failedPoints.add(p); // Cache result
35 return false;
36 }

Stackoverflow 上的几篇文章解释了从开始位置到结束位置有多少种方式，即 (r+c)!/(r!c!) 但我不明白为什么 Kayle 解释上述解决方案是 O(2^( r+c)) 和使用记忆成本 O(r*c)。有人可以为我解释清楚吗？如果您能提供帮助，我将不胜感激。

标签： java

解决方案

事实上，此类问题需要图表和 GIF 来完美地解释算法。不过，我会尽量用文字来解释。

  1. 它消耗 O(2^(r+c)) 因为它尝试了各种方式。您需要踩下 r 个单元格并向右踩下 c 个单元格才能到达目的地。一旦您了解您的路径是关于 (r+c) 步骤的，那么每个单元格都有两个选择：接受或离开。因此，时间复杂度为 O(2^(r+c))。
  2. 它消耗 O(r c) 因为使用了记忆。现在，您只需尝试每个单元一次，以找出该单元的最佳用途，并在您再次需要时从该结果中受益。由于您的网格有 rc个单元格，因此遍历所有单元格一次会消耗 O(r*c)。

我希望这可以帮助您弄清楚这个问题是什么。

推荐阅读