Робот в сетке большой O объяснение

Question

Я провел несколько исследований по этой проблеме, но не смог найти объяснения временной сложности.

При взломе 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 }

И при добавлении хэш-карты для кеширования неудачных точек из предыдущего вызова, почему это стоит всего 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 объясняют, сколькими способами вы можете go от начальной позиции до конца, что составляет (r + c)! / (R! c!), Но я не понимаю, почему Кейл объясняет, что вышеприведенное решение - O (2 ^ (r + c)), а стоимость мемоизации - O (r *c). Может ли кто-нибудь мне четко объяснить? Я был бы очень признателен, если бы вы могли помочь.

Answer 1

На самом деле, для таких задач нужны диаграммы и GIF-файлы, чтобы идеально объяснить алгоритм. Тем не менее, я изо всех сил постараюсь объяснить это словами.

1. Он потребляет O (2 ^ (r + c)), потому что пытается всячески. Вам нужно наступить на r ячеек вниз и на c ячеек вправо, чтобы добраться до места назначения. Как только вы поймете, что ваш путь составляет примерно (r + c) шагов, у каждой ячейки есть два варианта: принять или оставить. Таким образом, временная сложность равна O (2 ^ (r + c)).
2. Он потребляет O (r c), потому что используется мемоизация. Теперь вам нужно попробовать каждую ячейку только один раз, чтобы узнать, как лучше всего использовать эту ячейку и извлечь выгоду из этого результата, если он вам понадобится снова. Поскольку ваша сетка имеет r c ячеек, то при обходе всех ячеек один раз потребляется O (r *c).

Надеюсь, это поможет вам разобраться, с чем связана эта проблема.