一个时间复杂度的问题

为什么圆圈3那里得到O（1/6 n^3）呢？满足1<=k<=j<=i<=n的所有(i,j,k)有多少组，为什么三个变量一共有6种可能的大小关系呢？

当i=1时，内层for循环执行次数是1=1
当i=2时，内层for循环执行次数是1 + （1+2）=4
当i=3时，内层for循环执行测试是 1+（1+2）+（1+2+3）=10
当i=4时，内层for循环执行测试是 1+（1+2）+（1+2+3）+（1+2+3+4）=20
...
当i=n时，内层for循环执行测试是 1+（1+2）+（1+2+3）+（1+2+3+4）+ ...+(1+2+..+n)
相当于a(n)=a(n-1)+n(n+1)/2，这个数列最后a(n)的表达式为：
a(n)=n(n+1)(n+2)/6
时间复杂度取幂次最高的项就是 1/6n^3

3个变量全排列不是6种吗，你在想什么呀，高中知识

• 我从CSDN技能树中找了一些相关资料给你, 你可以看下:
• 相关参考资料: 复杂度

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632