weixin_38393017 2017-07-30 16:27 采纳率: 0%
浏览 6046

关于for语句算法执行次数的问题

如下代码段
for ( int i=0;i<N;i++)
for ( int j=i+1;j<N;j++)
for ( int k=j+1;k<N;k++)
if(xxxxxx)

            为什么这段算法的执行次数为 N(N-1)(N-2)/6 啊?这个/6是怎么算出来的呢?
  • 写回答

7条回答 默认 最新

  • a350062174 2017-08-01 03:25
    关注

    可以用中学数学计算:
    因为是3层循环:得到函数通式(一元3次函数): f(x)=a*x*x*x+b*x*x+c*x+d

    int x=3;
    int count=0;
    for ( int i=0;i<x;i++)
    for ( int j=i+1;j<x;j++)
    for ( int k=j+1;k<x;k++)
                count++;
    

    通过程序计算可得f(0)=0, f(1)=0,f(2)=0,f(3)=1 .有下面方程组:
    d=0
    a+b+c+d=0
    8a+4b+2c+d=0
    27a+9b+3c+d=1
    对方程组进行求解得到:
    a=1/6
    b=-1/2
    c=1/3
    d=0

    代入通式:f(x)=a*x*x*x+b*x*x+c*x+d可得
    f(x)=x*x*x/6-x*x/2+x/3
    进行分解就得到:
    f(x)=x(x-1)(x-2)/6

    所以这段代码的执行次数是 :N(N-1)(N-2)/6

    评论

报告相同问题?

悬赏问题

  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名