【算法设计与分析】08 序列求和的方法

16 篇文章 27 订阅
订阅专栏

本篇文章学习数列求和的一些方法。这些方法对后面学习算法的时间复杂度非常有帮助。

1. 数列求和公式

下面这几个数列求和公式都是高中学过的公式。

  • 等差、等比数列和调和级数

在这里插入图片描述

下面给出一个求和的例子,使用了一些高中都会的变换的技巧:

在这里插入图片描述

学习上面的公式,主要是为了解决算法的时间复杂度,下面以二分搜索的时间复杂度为例,讲解如何利用上面的公式求解出,时间二分搜索的时间复杂度(关于时间复杂度的概念,可以参看以前的文章: 【算法设计与分析】03 算法及其时间复杂度)。

1.1 二分搜索的时间复杂度求解

  • 假设二分数组为T[n],要搜索的数为:x。如下图是一个简单数组的搜索过程。

在这里插入图片描述
上述的二分搜索最终并没有找到要搜索的元素的位置。所以二分搜索的数据的输入情况,可以分为两种,一种是想要搜索的数x在数组中,一种是想要搜索的x不在数组中,那么一共就有2n+1中情况发生。如下图:

  • 左边是x在数组中,可以在任何一个位置出现,有n种情况。
  • 右边是x不在数组中,那么x出现在数组的两边或者在数组中两个元素的中间,就有n+1种情况
  • 所以一共有2n+1种输入情况。
    在这里插入图片描述

注意:上述,假设n=2k-1,只是为了方便后面的计算。

现在已经知道了总的输入,还需要知道总的输入对应的比较的次数,才能计算出时间复杂度。
由分析可以看出,比较t次的输入的个数为:

在这里插入图片描述

所以:

  • 对于t= 1,2…k-1,比较t次的输入有 :2t-1 个 (这个对应的是x在数组中的情况)
  • 对于x不在数组中的情况,需要比较的次数是k,那么比较k次的输入就是:2k-1+n+1个。(式子中的n+1是对应的不在数组中非空隙的个数,2k-1 对应的是x在数组中的情况,因为就算要找的数不在数组中,也要将数组比较完全一遍才能够知道)

那么总次数就等于:对每个输入乘以这个输入对应的次数并求和

假设n=2k-1 ,各种输入的概率相等,则二分搜索平均时间复杂度为A(n):

在这里插入图片描述

上述的计算过程用到了一开始学习的几个公式以及变换技巧,自己慢慢掌握。

上述的计算结果大家都不陌生了,正式二分搜索的平均时间复杂度:logn

2 估计和式上届的放大法

放大法在高中大家学的都很熟练应该。

  • 放大法:

在这里插入图片描述

  • 放大法的例子

在这里插入图片描述

3 估计和式渐近的界

以下方法用到了基本微积分的概念。

求上届
在这里插入图片描述

求下届
在这里插入图片描述

上面的上届和下届都是同一个级别的,所以:

在这里插入图片描述

4 总结

本文学习了序列求和的基本公式:

  • 等差数列
  • 等比数列
  • 调和级数

对于无法计算的序列和,可以采用放大法求上届,用积分做和式渐近的界

这些基本的计算方法对计数循环过程的基本运算次数很有帮助。也就是算法的时间复杂度了。

序列
dev_zyx的博客
05-19 411
题目: [编程题]序列序列和 题解: 代码: import java.util.*; public class 序列和 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNextInt()) { int N = sc.nextInt(); int L = sc.
牛客:序列
想握住此生辽阔
03-31 243
答题链接 https://www.nowcoder.com/practice/46eb436eb6564a62b9f972160e1699c9?tab=answerKey 题目描述 给出一个正整数N和长度L,找出一段长度大于等于L的连续非负整数,他们的和恰好为N。答案可能有多个,我我们需要找出长度最小的那个。 例如 N = 18 L = 2: 5 + 6 + 7 = 18 3 + 4 + 5 + 6 = 18 都是满足要求的,但是我们输出更短的 5 6 7 解题思路 我的思路是创建二维数组,利用动态规划的思
算法基础入门—序列求和
qq_40173649的博客
01-18 2279
序列求和 求和要注意两点:    1.数据规模大小    2.代码运行效率 问题描述 求1+2+3+…+n的值。 输入格式 输入包括一个整数n。 输出格式 输出一行,包括一个整数,表示1+2+3+…+n的值。 样例输
计算序列之和
算法与编程之美
07-02 725
问题描述有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13...求出这个数列的前20项之和。示例:输入:输入前二十项,并取两位小数。输出:32.662.算法描述给定两个起始数,分别赋值,然后套入循环里面,根据规律,分子为上一组分子和分母这个,并递推,直到第二十项,最后求和,得出结果。3. 实验讨论与结果找出规律,并根据规律写循环,再写出程序。a=1b=2s......
C语言序列求和
爱学习的JackYang的博客
11-16 7220
#include<stdio.h> int main() {     int n,sum=0;     printf("请输入你要输入的数字:");     scanf("%d",&n);     for(int i=1;i<=n;i++)     {         sum+=i;     }     printf("%d",sum);     return 0; } ...
python中常用的序列求和方法
qq_42420425的博客
08-07 4877
输入正整数n,输出1+2+3+……+n-1+n的和 函数求和 n = int(input('请输入想求和的数字:')) print(sum(range(1,n+1))) 高阶函数reduce from functools import reduce n = int(input('请输入想求和的数字:')) print(reduce(lambda a,b:a+b,list(range(1,n+1)))) #普通求和 n = int(input('请输入想求和的数字:')) sum = 0 fo
算法设计与分析-4动态规划金罐游戏.pptx
06-18
算法设计与分析-4动态规划金罐游戏.pptx 蛮力法(简单重复递归)和动态规划解决金罐问题 状态数组 子问题 状态方程 蛮力法(时间复杂度O(2n))和动态规划(时间复杂度O(n2)) 空间效率 当前序列相对最大金币值 通过...
算法设计与分析-4动态规划金罐游戏源代码.cpp
06-18
算法设计与分析-4动态规划金罐游戏源代码.cpp (1) 动态规划算法设计思想。 (2) 金罐游戏问题的动态规划解法。 通过本次实验,我尝试了使用蛮力法(简单重复递归)和动态规划解决金罐问题,在该过程中我加深了...
经典算法1(序列求和).c
05-01
经典算法1(序列求和).c
序列求和.zip
12-04
蓝桥杯VIP题和题解
论文研究-基于ARIMA的存储优化算法设计与实现.pdf
07-22
分析了SAN(storage area network)共享存储体系中I/O访问路径上可能存在的性能瓶颈,提出了采用ARIMA时间序列分析方法建立基于前馈的预测式控制机制,预测瓶颈发生趋势;通过改变存储子系统内的块映射关系来实现...
在线编程-连续数字求和
08-09
但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? ...
max-subsequence-sum:求最大子序列和的算法
06-03
最大子序列和该算法采用向量(数组)并找到它的最大子序列和: node max-subsequence-sum.js [2,-4,6,8,-10,100,-6,5]
算法引论:一种创造性方法.[美]Udi Manber(带详细书签).pdf
04-23
第5章提出了与归纳证明进行类比的算法设计思想;第6章到第9章分别给出了4个领域的算法,如序列和集合的算法、图算法、几何算法、代数和数值算法;第10章涉及归约,也是第11章的序幕,而后者涉及NP完全问题;第12章则...
图像序列中点目标实时检测算法 (2014年)
05-07
点目标检测在液体杂质检测中非常关键, 在分析现有图像点状目标检测算法的基础上, 研究了一种适用于图像序列的运动点目标多阈值检测算法, 在背景抑制的基础上, 首先采用自适应多阈值分类的方法提取多类疑似目标, 强化...
序列求和——算法
Hemx的博客
12-18 978
序列求和 题目描述 求1+2+3+…+n的值。 题目分析 说明:请注意这里的数据规模。 本题直接的想法是直接使用一个循环来累加,然而,当数据规模很大时,这种“暴力”的方法往往会导致超时。此时你需要想想其他方法。你可以试一试,如果使用1000000000作为你的程序的输入,你的程序是不是能在规定的上面规定的时限内运行出来。 本题另一个要值得注意的地方是答案的大小不在你的语言默认的整型(int)范围...
序列求和,求1+2+3+.....+n的值
冰冻非一日之寒
02-27 2401
一、求1+2+3+.....+n的值,代码如下:            方法一:        public class Main { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner Scanner=new
C语言实现,求序列数之和
Accompanyyl的博客
08-15 1146
C语言实现,求序列数之和
4-4 求序列
WangYutao的博客
08-28 1172
//求序列和 #include double fun(int a,int n); int main(int argc,char const *argv[]) { int a,n; scanf("%d%d",&a,&n); int i; double sum=0; for(i=1;i<=n;i++) { sum=sum+fun(a,i); } printf("sum=%.0f\n
python 求和算法
最新发布
09-12
### 回答1: 在 Python 中,可以使用内置的函数 `sum` 对数字序列求和。例如: ``` numbers = [1, 2, 3, 4, 5] total = sum(numbers) print(total) ``` 输出结果为: ``` 15 ``` 除了使用 `sum` 函数外,还可以使用 for 循环手动实现求和: ``` numbers = [1, 2, 3, 4, 5] total = 0 for number in numbers: total += number print(total) ``` 输出结果也为: ``` 15 ``` 如果需要对一个已知范围内的数字求和,可以使用等差数列求和公式: ``` n = 5 total = n * (n + 1) // 2 print(total) ``` 输出结果为: ``` 15 ``` ### 回答2: Python 求和算法是一个非常常见并且简单的算法。通常,我们可以使用 for 循环或者内置的 sum 函数来实现求和。 使用 for 循环方法求和可以按照以下步骤进行: 1. 定义一个变量 sum,用于保存求和结果。 2. 使用 for 循环遍历需要求和数列,将每个元素与 sum 相加,更新 sum 的值。 3. 循环结束后,sum 的值即为数列求和结果。 以下是一个使用 for 循环方法求和的示例代码: ```python def sum_algorithm(numbers): sum = 0 for num in numbers: sum += num return sum numbers = [1, 2, 3, 4, 5] result = sum_algorithm(numbers) print(result) # 输出结果为 15 ``` 另外,Python 中还提供了内置的 sum 函数来实现求和。该函数接受一个数列作为参数,并返回数列求和结果。以下是使用内置 sum 函数求和的示例代码: ```python numbers = [1, 2, 3, 4, 5] result = sum(numbers) print(result) # 输出结果为 15 ``` 不管是使用 for 循环还是内置函数 sum,Python 提供了很多灵活的方式来实现求和,使得求和算法变得非常简单和方便。 ### 回答3: Python 求和算法就是对一组数字进行加法运算,得到它们的总和。使用Python编程语言,有多种方法可以实现求和算法。 一种常见的方法是使用循环来遍历给定的数字列表,并将它们逐个相加。例如,假设有一个数字列表 `[1, 2, 3, 4, 5]`,我们可以使用循环来实现求和算法如下: ``` numbers = [1, 2, 3, 4, 5] total = 0 # 初始求和结果为0 for num in numbers: total += num # 将每个数字加到总和上 print(total) # 输出总和结果 ``` 另一种更简洁的方法是使用Python内置的`sum`函数,该函数可以对一个迭代对象进行求和。例如,我们可以像这样使用`sum`函数实现相同的求和算法: ``` numbers = [1, 2, 3, 4, 5] total = sum(numbers) # 使用sum函数对数字列表进行求和 print(total) # 输出总和结果 ``` 总的来说,Python 求和算法可以通过循环遍历数字列表并逐个相加,或者使用内置的`sum`函数来实现。这些方法都能够很方便地求出一组数字的总和。

“相关推荐”对你有帮助么?

  • 非常没帮助
  • 没帮助
  • 一般
  • 有帮助
  • 非常有帮助
提交
写文章

热门文章

  • 【C++学习详细教程目录】 25022
  • MarkDown编辑器中数学公式与符号-LaTeX 各种数学命令,符号 22858
  • C++从入门到进阶近100本书推荐电子书pdf 22023
  • 【C++深度剖析教程5】C++中类的静态成员函数 21929
  • C语言实现位数组(bit数组)与位数组的简单应用举例 21677

分类专栏

  • mysql技术内幕 2篇
  • 阿里云账号信息
  • 美团工作总结
  • 算法设计与分析 16篇
  • C++深度剖析学习记录 41篇
  • 常见笔试算法题分析记录 9篇
  • 打通Linux脉络之进程 线程 任务调度 5篇
  • Git、GitHub、GitLab学习专栏 10篇
  • C语言深度剖析学习记录 38篇
  • 软件开发底层知识修炼 28篇
  • 数据结构与算法(C++/java实现) 3篇
  • 离散数学中的数据结构与算法 11篇
  • 剑指offer总结(C++/Java 多种解法) 14篇
  • Linux环境编程
  • 数据结构与算法学习笔记 8篇
  • 操作系统学习笔记 5篇
  • C语言学习笔记 41篇
  • 总结 25篇
  • 面试常见问题 4篇
  • 常见笔试算法题分析记录 12篇
  • 剑指offor 14篇
  • OS学习笔记之X86汇编 41篇
  • 软件开发之底层知识修炼 29篇
  • 转载的程序员常用技巧 15篇
  • Git、GitHub、GitLab学习记录 10篇
  • 离散数学中的数据结构与算法 10篇
  • java入门实践总结 2篇
  • spring学习 1篇

最新评论

  • 【OS修炼指南目录】----《X86汇编语言-从实模式到保护模式》读书笔记目录表

    jdiejbxiej: 大佬救命了表情包

  • 【OS修炼指南目录】----《X86汇编语言-从实模式到保护模式》读书笔记目录表

    wobudao_h: 真救命了,学校老师讲的太抽象了

  • 【C++深度剖析教程4】C++的二阶构造模式

    jokercsj: 误人子弟

  • 【C语言进阶深度学习记录】三十一 数组作为函数参数时退化为指针

    CSDN-Ada助手: 多亏了你这篇博客, 解决了问题: https://ask.csdn.net/questions/8017640, 请多输出高质量博客, 帮助更多的人

  • 【OS学习笔记】七 Bochs的下载、安装和配置

    圣人无名666: 我也想知道vhd在哪里啊?

您愿意向朋友推荐“博客详情页”吗?

  • 强烈不推荐
  • 不推荐
  • 一般般
  • 推荐
  • 强烈推荐
提交

最新文章

  • 【MySQL原理解析】01. 一条SQL查询语句是如何执行的
  • 【mysql技术内幕1】mysql基础架构-一条SQL查询语句是如何执行的
  • 掘金浏览器插件安装图文教程
2021年2篇
2020年1篇
2019年112篇
2018年177篇
2017年14篇

目录

目录

评论 1
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43元 前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值

聚圣源姓宋的男孩起什么名字好赵英俊得了什么病一二三四五线城市名单万古丹帝好寓意的成语起名子网址你懂我意思正能量重庆13岁男孩被茅山术炼成小鬼9月18日勿忘国耻我要当八路电视剧全集澳大利亚足球酒店管理软件起名党支部人数一般不超过多少人神龙传说1.2a测试版总是的近义词在线起名测试免费2021年男孩起名字好寓意的字暗黑破坏神2v1.13女孩起什名免费公司起名测试傅姓起名字大全陈奕迅经典歌词梦幻坐骑任务鼠宝宝七月起名李字起名字大全男孩纲手本子我还要起名网龙年宝宝起名大全男孩beyondcompare破解版姓夏的名字怎么起属属鼠的人起名字淀粉肠小王子日销售额涨超10倍罗斯否认插足凯特王妃婚姻让美丽中国“从细节出发”清明节放假3天调休1天男孩疑遭霸凌 家长讨说法被踢出群国产伟哥去年销售近13亿网友建议重庆地铁不准乘客携带菜筐雅江山火三名扑火人员牺牲系谣言代拍被何赛飞拿着魔杖追着打月嫂回应掌掴婴儿是在赶虫子山西高速一大巴发生事故 已致13死高中生被打伤下体休学 邯郸通报李梦为奥运任务婉拒WNBA邀请19岁小伙救下5人后溺亡 多方发声王树国3次鞠躬告别西交大师生单亲妈妈陷入热恋 14岁儿子报警315晚会后胖东来又人满为患了倪萍分享减重40斤方法王楚钦登顶三项第一今日春分两大学生合买彩票中奖一人不认账张家界的山上“长”满了韩国人?周杰伦一审败诉网易房客欠租失踪 房东直发愁男子持台球杆殴打2名女店员被抓男子被猫抓伤后确诊“猫抓病”“重生之我在北大当嫡校长”槽头肉企业被曝光前生意红火男孩8年未见母亲被告知被遗忘恒大被罚41.75亿到底怎么缴网友洛杉矶偶遇贾玲杨倩无缘巴黎奥运张立群任西安交通大学校长黑马情侣提车了西双版纳热带植物园回应蜉蝣大爆发妈妈回应孩子在校撞护栏坠楼考生莫言也上北大硕士复试名单了韩国首次吊销离岗医生执照奥巴马现身唐宁街 黑色着装引猜测沈阳一轿车冲入人行道致3死2伤阿根廷将发行1万与2万面值的纸币外国人感慨凌晨的中国很安全男子被流浪猫绊倒 投喂者赔24万手机成瘾是影响睡眠质量重要因素春分“立蛋”成功率更高?胖东来员工每周单休无小长假“开封王婆”爆火:促成四五十对专家建议不必谈骨泥色变浙江一高校内汽车冲撞行人 多人受伤许家印被限制高消费

聚圣源 XML地图 TXT地图 虚拟主机 SEO 网站制作 网站优化