为了账号安全,请及时绑定邮箱和手机立即绑定

如何找到这个嵌套for循环的复杂性?

如何找到这个嵌套for循环的复杂性?

慕码人2483693 2022-09-22 19:24:34

我对这个循环有点困惑。给定一个数字n,我们必须找出指令执行多少次。for


int j = 0;

for(int p = 0; p < n*n; p++ )

{

    for(int q = 0; q < p; q++ )

    {

        j++;

    }

}

我的回答是.这个答案正确吗?O(n^4)


查看完整描述

1 回答

?
人到中年有点甜

TA贡献1562条经验 获得超7个赞

您可以为时间复杂度 编写相关的西格玛。因此,您的答案对于说明的数量是正确的。T(n) = sum_{p = 1}{n^2} sum_{q=1}{p} (1) = sum_{p=1}{n^2} (p) = 1 + 2 + 3 + ... + n^2 = n^2(n^2 + 1)/2 = Theta(n^4)



查看完整回答
反对 回复 4天前

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信