首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >迭代二项式系数的时间复杂度是多少?

迭代二项式系数的时间复杂度是多少?
EN

Stack Overflow用户
提问于 2018-11-10 01:58:25
回答 1查看 448关注 0票数 1

用动态规划法求解迭代二项式系数的时间复杂度是多少?如何找到它呢?我可以说下面的代码是使用动态规划迭代二项式系数的示例吗?!!

代码语言:javascript
运行
复制
class BinomialCoefficient 
{ 
    // Returns value of Binomial Coefficient C(n, k) 
    static int binomialCoeff(int n, int k) 
    { 
        int C[][] = new int[n+1][k+1]; 
        int i, j; 

        // Calculate value of Binomial Coefficient in bottom up manner 
        for (i = 0; i <= n; i++) 
        { 
            for (j = 0; j <= min(i, k); j++) 
            { 
                // Base Cases 
                if (j == 0 || j == i) 
                    C[i][j] = 1; 

                // Calculate value using previosly stored values 
                else
                    C[i][j] = C[i-1][j-1] + C[i-1][j]; 
            } 
        } 

        return C[n][k]; 
    } 

    // A utility function to return minimum of two integers 
    static int min(int a, int b) 
    { 
        return (a<b)? a: b; 
    } 

    /* Driver program to test above function*/
    public static void main(String args[]) 
    { 
        int n = 5, k = 2; 
        System.out.println("Value of C("+n+","+k+") is "+binomialCoeff(n, k)); 
    } 
}  
EN

回答 1

Stack Overflow用户

发布于 2018-11-10 02:10:27

你填充表的梯形部分(帕斯卡三角形)。空中飞人的高度是k,长底是n,短底是n-k

因此,它包含k*(n+(n-k))/2项,算法进行相同数量的单元格操作,并且复杂度为O(nk)

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/53231040

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档