时间戳

首页 > 解决方案 > 带有记忆的递归斐波那契的空间复杂度？

java - 带有记忆的递归斐波那契的空间复杂度？

问题描述

我有这两种方法可以找到给定数字“n”的斐波那契数列。一种是使用记忆。

我想知道这两种方法的空间复杂度有何不同：

    public static int fib(int n, int[] mem){

    if(n ==0 || n ==1 ){
        return n;
    }

    if(mem[n] > 0 ) {
        return mem[n]);
    }

    mem[n] = fib(n-1,mem) + fib(n-2,mem);

    return mem[n]; 

}

没有记忆：

public static int fib(int n){

    if(n ==0 || n ==1 ){
        return n;
    }

   return fib(n-1) + fib(n-2);


}

标签： javafibonaccispace-complexity

解决方案

直接内存使用是不言而喻的 - 使用 memoization fib 中的每个值将只计算一次，因此您的空间复杂度将为 o(n)，其中 n 是 fib 的输入数字（memoization 数组将保存 n 个数字）。

没有记忆 - 不需要额外的内存（缺点是许多冗余计算）。

传递给每个递归调用的记忆数组是同一个数组..还是该数组的副本？如果数组的副本被传递......空间复杂度将> O（n）。

您将相同的数组引用传递给递归调用。

这意味着您的空间复杂度为 o(n)。如果您要创建一个新数组并传递它，您的记忆将无法工作，因为您必须将更新后的新数组的结果与前一个/s 合并。

推荐阅读