> 数学 >
设计一个算法,计算数列2-4+6-8+10……±m的∑值并返回,要求时间复杂度为O(1).
设计一个算法,计算数列2-4+6-8+10……±m的∑值并返回,该数列存放在一个整型数组中.要求时间复杂度为O(1).
谢大神解答!
人气:294 ℃ 时间:2020-09-06 21:16:20
解答
如果一共有n个数,首先判断n奇偶性;
如果n是偶数,那么两两一组,每一组的和是-2(2-4,6-8,.),
这样前n个数的和就是 -2*(n/2) ;
如果n是奇数,n-1就是偶数,那么前n-1个数有 (n-1)/2 组,
由上述讨论可知,前n-1个数的和是:-2*((n-1)/2);
而最后一个数(也就是第n个数)是正的,即 2n ,
这样前n个数的和就是:-2*((n-1)/2)+2n
这个算法的结果只要计算一个值:-2*(n/2) 或 -2*((n-1)/2)+2n ,时间复杂度当然就是是O(1);
推荐
猜你喜欢
© 2024 79432.Com All Rights Reserved.
电脑版|手机版