Как рассчитать временную сложность рекурсий с помощью memoization?

Question

Какова временная сложность кода, указанному ниже? Я знаю, что он имеет рекурсивный вызов несколько раз, поэтому он должен, вероятно, быть 3^n, но все же каждый раз он инициализирует массив длины n, который используется последним, и это меня смущает. Какая должна быть временная сложность, если мы добавим дополнительный массив для применения memoization? Это ниже - решение для задачи Hackerrank Java 1D Array (Hard).

public static boolean solve(int n, int m, int[] arr, boolean[] visited, int   curr) { 
    if (curr + m >= n || curr + 1 == n) { 
     return true; 
    } 

    boolean[] newVisited = new boolean[n]; 
    for (int i = 0; i < n; i++) { 
     newVisited[i] = visited[i]; 
    } 

    boolean s = false; 
    if (!visited[curr+1] && arr[curr+1] == 0) { 
     newVisited[curr+1] = true; 
     s = solve(n,m,arr,newVisited,curr+1); 
    } 
    if (s) { 
     return true; 
    } 
    if (m > 1 && arr[curr+m] == 0 && !visited[curr+m]) { 
     newVisited[curr+m] = true; 
     s = solve(n,m,arr,newVisited,curr+m); 
    } 
    if (s) { 
     return true; 
    } 
    if (curr > 0 && arr[curr-1] == 0 && !visited[curr-1]) { 
     newVisited[curr-1] = true; 
     s = solve(n,m,arr,newVisited,curr-1); 
    } 
    return s; 
} 

Answer 1

Ваша реализация действительно имеет экспоненциальную сложность. Я не думал об этой части вашего вопроса. Возможно, немного утомительно придумать худший сценарий. Но один сценарий «по крайней мере-очень-плохой» должен состоять в том, чтобы первые n-m элементов в arr устанавливались в 0 и последние m элементы, установленные в 1. Много разветвлений прямо там, на самом деле не используя механизм memoization. Я бы предположил, что ваше решение по крайней мере экспоненциально в n/m.

Вот еще одно решение. Мы можем перефразировать проблему как графическую. Пусть элементы в вашем массиве являются вершинами графика , направленным на график, и пусть существует граница между каждой парой вершин одной из следующих форм: (x,x-1), (x,x+1) и (x,x+m), если оба конца такого ребра имеют значение 0 Добавьте на ваш график дополнительную вершину t. Также добавьте ребро из каждой вершины со значением 0 в {n-m+1,n-m+2,...,n} до t. Таким образом, у нас есть не более 3n+m ребер на нашем графике. Теперь ваша проблема эквивалентна определению того, существует ли путь от вершины 0 до t в графике, который мы только что создали. Это может быть достигнуто путем запуска глубины первого поиска, начиная с вершины 0, имеющей сложность O(|E|), которая в нашем случае равна O(n+m).

Возвращаясь к вашему решению, вы делаете почти то же самое (возможно, не осознавая этого). Единственное реальное различие заключается в том, что вы копируете массив visited в newVisited и, таким образом, никогда не используете все эти мемуары: p Итак, просто устраните newVisited, используйте visited везде, где вы используете newVisited, и проверьте, что происходит.