算法:从1到N之间能被2整除不能被3整除的数的总和

时间:2022-07-26 22:42:06
  
无聊,做一个练习的时候随便想到的。
1. 如果是在Pentium4  2GHz的计算机做... 
    时间复杂度为O(n)    
    ii=1;
   while(ii<=N){
    if( ii%2==0 && ii%3!=0 ){
    summ+=ii;
    document.writeln(ii); //输出每个符合条件的数.
    }
    ii++;
    }

<HR>
2. 如果计算机不太好,只有Pentium3  1GHz主频...
    时间复杂度为时间复杂度为O(n/2),同数量级的复杂度,不过执行时间少了50%。

    ii=2;
   while(ii<=N){
    if( ii%3!=0 ){
    summ+=ii;
    document.writeln(ii); //输出每个符合条件的数.
    }
    ii++2;
    }

<HR>
3. 如果是我自己做...
   所以说我还是比计算机聪明那么一点点,自己算,一个循环都没有,时间复杂度当然为O(1)了。

   R=Math.floor(N/6);
   K=Math.floor(Math.floor(N%6)/2);
   summ=6*Math.pow(R,2)+(6*R+2)*K+K*(K-1);
   说明: Math.floor(int a)作用是取不大于a的最大整数,相当于把a的小数直接截掉.

    实际执行中,我本机为1GHz的CPU,当N超过5,000,000的时候, 算法1基本上可以让我的计算机差点宕机,算法2可以到10,000,000, 执行时间大约要5分钟左右.当然,算法3是没有任何问题的,数目只要不溢出就ok,基本上不需要时间,执行时间绝对在1s以下. 唉,没办法,这就是人和计算机的区别.