小编Tho*_*ody的帖子

这是一个关于课程作业的问题,所以宁愿你没有完全回答这个问题,而是提出改进我当前算法的运行时复杂性的技巧.

我收到了以下信息:

函数g(n)由g(n)= f(n,n)给出,其中f可以递归地定义

我用以下代码递归地实现了这个算法:

public static double f(int i, int j) 
{

    if (i == 0 && j == 0) {
        return 0;
    }
    if (i ==0 || j == 0) {
        return 1;
    }

    return ((f(i-1, j)) + (f(i-1, j-1)) + (f(i, j-1)))/3;
}

这个算法给出了我正在寻找的结果,但效率极低,我现在的任务是提高运行时间的复杂性.

我写了一个算法来创建一个n*n矩阵然后计算每个元素直到[n] [n]元素,然后它返回[n] [n]元素,例如f(1,1)会返回0.6重复出现.[n] [n]元素重复为0.6,因为它是(1 + 0 + 1)/ 3的结果.

我还创建了一个结果从f(0,0)到f(7,7)的电子表格,如下所示:

现在虽然这比我的递归算法快得多,但它创建一个*n矩阵的开销很大.

任何有关如何改进此算法的建议将不胜感激!

我现在可以看到有可能使算法O(n)复杂,但是有可能在不创建[n] [n] 2D数组的情况下计算出结果吗？

我已经在Java中创建了一个在O(n)时间和O(n)空间中运行的解决方案,并且在我递交课程以阻止任何抄袭之后将发布解决方案.