0

对于以下代码：

 s = 0 ;  
 for(i=m ; i<=(2*n-1) ; i+=m)  {  
      if(i<=n+1){ 
        s+=(i-1)/2 ; 
      }  
      else{ 
        s+=(2*n-i+1)/2 ; 
      }    
 }

我想将代码的复杂性从 更改O(n) 为O(1). 所以我想消除 for 循环。但是，由于总和s存储了类似(i-1)/2或这样的值，(2*n-i+1)/2因此消除循环涉及对每个 (i-1)/2or的底值进行繁琐的计算(2*n-i+1)/2。这样做对我来说变得非常困难，因为我可能推导出了错误的楼层总和公式。你能帮我把复杂性从O(n)变成O(1). 或者请帮我做这个楼层总结。有没有其他方法可以降低复杂性？如果是……那怎么办？

4

2 回答 2

2

我的方法是首先编写特征测试，断言为不同的值m和产生的值n，然后开始重构。

您的主循环基于中途（if(i<=n+1)选择）而改变了逻辑，因此我首先将其拆分为两个循环。

然后，您在每个生成的循环中都有一个主要根据i是偶数还是奇数而变化的计算。将每一个拆分为另外 2 个循环，将它们分开，并且地板计算可能更容易理解。或者，您可能会看到一种重复值的模式，可以让您以不同的方式简化这些循环。

每个生成的循环都可能类似于算术级数的总和，因此您可能会发现它们可以被完全不需要循环的封闭形式计算所取代。

当您沿着这条路径前进时，您还可以重构以将部分计算提取为函数。在提取它们时为它们编写特征测试。

继续运行所有测试，您可能能够将其减少为简单计算的总和，然后通过简单的旧算术进一步减少。

于 2012-05-05T16:19:15.943 回答
2

正如唐罗比所说，你的问题有一个简单的旧算术解决方案。让我向您展示如何处理 i 的第一个值。

* 编辑 2：下部代码 *

    for(int i=m ; i<= n+1 ; i+=m)//old computation
          s+=(i-1)/2 ;


    int a = (n+1)/m; // maximum value of i
    int b = (a*(a+1))/2; //
    int v = 0;
    int p;
    if(m % 2 == 0){
        p = m/2;
        v = b*p-a; // this term is always here
    }
    else{
        p = (m - 1)/2;
        int sum1 = ((a/2)*(a/2 +1))/2; 
        int sum2 =  (((a-1)/2)*((a-1)/2 +1))/2;  

        v = b*p -a ;// this term is always here
        v+= sum1 + a/2; //sum( 1 <= j <= a )(j-1), j pair
        v+= sum2; //sum( 1 <= j <= a )(j-1), j impair
    }
    System.out.println( " Are both result equals ? "+ (s == v));

我怎么想出来的？我拿

 for(i=m ; i<= n+1 ; i+=m)
      s+=(i-1)/2 ;

我做出改变

 for(j=1 ; j*m <= n-1 ; j++)
     s+=(j*m-1)/2 ;

我摆姿势a=Math.floor(n+1/m)。有3种情况：

  1. m 是对，则循环的内部是s+= p*j。结果是

     b(a*(a+1))/2 -a

  2. m 是 impair 并且迭代器 j 是 pair

  3. m 为 impair 且迭代器 j 为 impair 当 m 为 impair 时，您可以编写m = 2p + 1并且循环的内部变为

     s+= p*j + (j-1)/2

p*j与以前相同，现在您需要通过假设 j 始终为 pair 或 j 始终为 impair 并将两个值相加来打破除法。

您需要计算的下一个循环是

 for(int i=a+1 ; i<= (2*n-1) ; i+=m)// a is (n+1)/m
    s+=(2*n-i+1)/2;

这与

 for(int i=1 ; i<= (2*n-1)-a ; i+=m)
    s+= (2n-a)/2 - (i-1)/2;

这个循环类似于第一个循环，所以没有太多工作要做......确实这很乏味......

于 2012-05-05T18:29:30.687 回答