算法:从1到N之间能被2整除不能被3整除的数的总和
无聊,做一个练习的时候随便想到的。
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以下. 唉,没办法,这就是人和计算机的区别.