将嵌套for循环转换为低于O(n ^ 3)

发布时间：2020-12-16 10:03:17 所属栏目：百科来源：网络整理

导读：所以,我有这个代码,我需要让它运行时间复杂度小于O(n ^ 3).我刚刚开始学习复杂性,我真的不知道该怎么做. int n,i,j,k,x=0;printf("Type n: n");scanf("%d",n);for(i=1; in; i++){ for(j=1; ji; j++) { for(k=1; kj; k++) { x=x+1; } }}printf("%dn",x); 我

所以,我有这个代码,我需要让它运行时间复杂度小于O(n ^ 3).我刚刚开始学习复杂性,我真的不知道该怎么做.

int n,i,j,k,x=0;
printf("Type n: n");
scanf("%d",&n);


for(i=1; i<n; i++)
{
    for(j=1; j<i; j++)
    {
        for(k=1; k<j; k++)
        {
            x=x+1;
        }
    }
}
printf("%dn",x);

我想我明白为什么它是O(n ^ 3),但我真的不知道如何让它更有效率.我试过把它变成递归函数,有可能吗？

解决方法

你为每个i,k的结果加1,0 << k< j<我< ?.选择(n-1,3)这样的i,k值(对于{1,2,...,n-1}的大小3的每个子集一个). (这里“选择”二项式系数函数). 因此,如果n为正,则可以选择(n-1,3)替换基于循环的计算,n = 1,3(n-2)(n-3)/ 6.

int n;
printf("Type n: n");
scanf("%d",&n);
printf("%dn",n > 0 ? (n-1)*(n-2)*(n-3)/6 : 0);

这是O(1)计算结果,O(log N)输出它(因为结果有O(log N)个数字).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!