题目

设计一个算法,计算数列2-4+6-8+10……±m的∑值并返回,要求时间复杂度为O(1).
设计一个算法,计算数列2-4+6-8+10……±m的∑值并返回,该数列存放在一个整型数组中.要求时间复杂度为O(1).
谢大神解答!

提问时间：2021-02-25

答案

如果一共有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)；