是否可以递归地计算时间复杂度为 O(n) 的卢卡斯数？

Question

我有一个 homework assignment 来计算卢卡斯数。我怎样才能使我的算法 O(n) 同时保持递归？

这是他给出的提示：

在考虑这个问题时，我想我会保留我的主 for 循环并让它存储 2 个数字，然后再计算一个数字，但那将是迭代的。

这是我现在的代码：

lucas(n) {  
    return 2 if n = 0;
    return 1 if n = 1;
    return lucas(n - 1) + lucas(n - 2);
}
main(String args[]) {
    for (int i = 0; i<=10; i++)
        print(lucas(i*5));
}

（代码是这样写的，以防抄袭。）

Answer 1

我认为这个问题的 Memoized 解决方案是 O(n)，因为 n 的每个解决方案将被计算不超过一次。

“技巧”是将 lucas(n) 的结果存储在映射中，以便在恒定时间 O(1) 中检索先前计算的结果，并计算一次新值。

(只有当值不在映射中时才需要计算完整的解决方案)

public class MemoizedLucas {
    private static Map<Integer, Integer> results = new HashMap<>();

    /**
     * @param args
     */
    public static void main(String[] args) {
        // add base cases to map
        results.put(0, 2);
        results.put(1, 1);

        // compute lucas number
        lucas(10);
        System.out.println(results);
    }
    // The lucas function will be called at most 2*n times - O(2*n) is still considered liner time. 
    public static int lucas(int n) {
        
        Integer result = results.get(n);
        if (result != null) return result; // return value if in map

        int a = lucas(n - 1);
        int b = lucas (n - 2);
        results.put(n , a + b);
        return results.get(n);
    }
}

如果打印出来，本程序输出序列的前10个数是：

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123

Answer 2

提示是定义一个递归 G 函数，并采用两个 Lucas 值作为 G 结果。然后可以将 lucas 函数定义为对 G.

的调用

如你所见，G 是 O(N)。

int lucas(int n) { return g(n)[0]; }
int[] g(int n) { ... recursiveG ... }

Answer 3

由于这是作业，我不会post将解决方案作为代码，但我希望我能展示它的路径。

给定的提示使用具有 2 个值的向量 - 在 Java 中我们可以使用数组（因为方法不能 return 只有两个值）。该方法需要 n.

的值

int[] calc(int n) {
    // TODO
}

公式Gn = M X Gn-1 - M是给定的矩阵，而Gn = [An , Bn]（An = Ln和Bn = Ln-1） - 我们可以改写为
[An , Bn] = [[1,1] [1,0]] X [An-1 , Bn-1] 或

An = 1*An-1 + 1*Bn-1 = An-1 + Bn-1 和
Bn = 1*An-1 + 0*Bn-1 = An-1

该方法将使用 n-1 调用自身，除非 n == 0，以获得 [An-1,Bn-1]，然后使用上述公式计算输出数组 [An,Bn]。

n=0 的初始数组应该是 [2,-1]（在提示中又名 G0。）

（因为 Gn 只依赖于 Gn-1 纯递归解是 O(n) - 不像通常的计算卢卡斯数的方法Ln 取决于 Ln-1 和 Ln-2)

我完全忽略了第二个提示并使用了上面的 int[] - 但不要忘记考虑 int 是否能够表示 L500
（有提示表示不会）

是否可以递归地计算时间复杂度为 O(n) 的卢卡斯数？

Is it possible to calculate Lucas numbers recursively with time complexity O(n)?

java

recursion

big-o