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

Question

Какова временная сложность кода ниже? Я знаю, что у него есть рекурсивный вызов несколько раз, поэтому, вероятно, он должен быть равен 3^n, но все равно каждый раз он инициализирует массив длины n, который используется последним, и это меня немного смущает. Какой должна быть временная сложность, если бы мы добавили дополнительный массив для применения мемоизации? Ниже приведено решение задачи 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. Много разветвлений, не использующих механизм запоминания. Я полагаю, что ваше решение по крайней мере экспоненциально в 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 и проверь что получится.