weixin_38393017
weixin_38393017
采纳率27.3%
2017-07-30 16:27 阅读 4.6k

关于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 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

    点赞 2 评论 复制链接分享
  • shen_wei shen_wei 2017-07-31 07:14
        int N = 5,nCount = 0;
        for (int i = 0;i < N;i ++)
        {
            for (int j = i + 1;j < N;j ++)
            {
                for (int k = j + 1;k < N;k ++)
                {
                    nCount ++;
                }
            }
        }
        printf("%d",nCount); 
    

    使用的来测试。。。最内层的表达式决定了nCount的值。。。

    点赞 1 评论 复制链接分享
  • fu_fei_wen fufeiwen 2017-07-31 00:55

    for ( int i=0;i<N;i++)
    for ( int j=i+1;j<N;j++)
    for ( int k=j+1;k<N;k++)
    以上循环次数是N(N-1)(N-2)
    而 /6 ,但从你发出来的,看不出来,是否跟判断条件有关?

    点赞 评论 复制链接分享
  • a415547421 Ujxiao0 2017-07-31 01:30

    i=N-3, 次数 1, i=N-4 1+2, i=N-5 1+2+3 .
    然后I=0 是 1+。。。+N-2

    即(N-2)x1+(N-3)x2........

    1x n+2x(n-1).....的结果是n(n+1)(n+2)/6
    这个代进去就是(N-2)(N-1)N/6
    大概是这样,中间的个数没仔细算,思路是这样啦。

    点赞 评论 复制链接分享
  • liman001 liman001 2017-07-31 01:37

    我觉得是N(N-1)(N-2)/3
    思路如下:
    当i=0, 执行的次数为(N-1)(N-2),当i=1, 执行的次数为(N-2)(N-3)
    当i=2, 执行的次数为(N-3)(N-4),……………………
    当i=N-3, 执行的次数为2×1
    当i>=N-2,不满足k<N的条件,不再执行
    总共执行次数为2×1+3×2+……+(N-2)(N-3)+(N-1)(N-2)=1×2+2×3+……+(N-2)(N-1)
    根据计算公式1*2+2*3+3*4+...+n(n+1)=(n+2)(n+1)n/3
    可得2×1+3×2+……+(N-2)(N-3)+(N-1)(N-2)=1×2+2×3+……+(N-2)(N-1)=((N-2)+2)((N-2)+1)(N-2)/3=N(N-1)(N-2)/3.

    点赞 评论 复制链接分享
  • a415547421 Ujxiao0 2017-07-31 01:49

    -i=0的时候明显不是(N-1)(N-2)每层都有依赖的,你这样是说每个最里面的循环每次都有N-2明显是错的,i=0时不是每个j都有N-2次的

    点赞 评论 复制链接分享
  • qq_39551595 DoubleAlive 2017-07-31 02:07

    我觉得这个代码的意思是:N(N-1)(N-2) 这个代表整个最外层 for 循环执行的次数,而之所以 /6 则是因为 /6 之后就变成了代码的有效执行次数,也就是最内层的 for 循环,我们都知道,要执行的代码都是放在最内层的 for 循环里面,而最内层的执行次数就是最外层执行次数 /6

    点赞 评论 复制链接分享

相关推荐