algorithm - 如何使用内存计算递归的时间复杂度？

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

您的实现似乎确实具有指数级的复杂性。我并没有真正考虑过你问题的这一部分。提出最坏的情况可能有点乏味。但是一个“至少相当糟糕”的场景是将 arr 中的第一个 n-m 元素设置为 0，将最后一个 m元素设置为 1。那里有很多分支，并没有真正利用内存机制。我猜你的解决方案至少是 n/m 的指数。

这是另一种解决方案。我们可以将问题改写为图形问题。让数组中的元素成为有向图的顶点，并让以下形式之一的每对顶点之间有一条边:(x,x-1)、(x,x+1) 和 (x,x+m)，如果这样一条边的两端的值为 0。添加一个额外的顶点 t 到你的图表。还从 {n-m+1,n-m+2,...,n} 中每个值为 0 的顶点添加一条边到 t。所以我们的图中只有 3n+m 条边。现在，你的问题等同于确定我们刚刚构造的图中是否存在从顶点 0 到 t 的路径。这可以通过从顶点 0 开始运行深度优先搜索来实现，复杂度为 O(|E|)，在我们的例子中为 O(n+ m).

回到您的解决方案，您正在做几乎相同的事情(可能没有意识到)。唯一真正的区别是您正在将 visited 数组复制到 newVisited 中，因此永远不会真正使用所有内存:p 所以，只需删除 newVisited , 在使用 newVisited 的任何地方使用 visited 并检查会发生什么。