设计一个算法,计算数列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);
推荐
- 用数列计算方法计算1+2+3+···+300的和
- 根据时期数列计算序时平均数应采用什么方法
- 数列运算方法
- 设计一个算法,看下面数列 -2,3,4,23,-18,25,4,-4,1,8,17,-20.求出数据8在该数列的第几项.
- 已知数列1,1,2,3,5,8,13,21,.设计一个算法求出该数列的前100项和
- 100-(□÷16+12+4)=47 简便运算
- 回忆诗句怎么形容
- 王大伯种了一块蔬菜地共有150平方米,其中种的白菜占45%,其中种的萝卜占35%,余下种的芹菜有多少平方米?
猜你喜欢