algorithm - 将复杂度从 O(n) 更改为 O(1)

Question

对于以下代码:

 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 loop 。但作为总和 s 存储像 (i-1)/2 或 (2*n-i+1)/2 这样的值，因此消除了循环涉及对每个 (i-1)/2 或 (2*n-i+1)/2 的底值进行繁琐的计算。这对我来说变得非常困难，因为我可能推导出错误的楼层总和公式。你能帮我把复杂度从 O(n) 改成 O(1) 吗？或者请帮我做这层楼的总结。还有其他方法可以降低复杂性吗？如果是...那么如何？

Answer 1

正如 Don Roby 所说，您的问题有一个简单的旧算术解决方案。让我告诉你如何为 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是pair，则循环内部是s+= p*j。结果是

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

2. m是impair，迭代器j是pair

3. m 是 impair 并且迭代器 j 是 impair当 m 受损时，可以写成 m = 2p + 1 循环内部变为

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

p*j 与之前相同，现在您需要通过假设 j 总是对或 j 总是损害并对两个值求和来打破除法。

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

 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;

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