求区间和aneasyproblem4.ppt
《求区间和aneasyproblem4.ppt》由会员分享,可在线阅读,更多相关《求区间和aneasyproblem4.ppt(7页珍藏版)》请在三一文库上搜索。
求区间和 an_easy_problem4,报告人学号:031302427 姓名:阮芳健 报告时间:9月9日,问题描述,给你一个序列的数,求某一段区间的和。 输入:两个正整数n 和m 。(n 表示这个序列的数的个数。m 表示几次询问。) 范围:(1=n,m=100000),对问题的理解和分析,明确要求:求某一段区间a,b的和; 分析: 法一:用数组存数列中的元素,给出区间时,再一个一个累加; 法二:用数组存前 i 项的和,给出指定区间就可以直接用对应的两个元素值相减,就是所得结果。,算法与数据结构的选取,n 的值最大可以达到100000,数据值n比较大时,方法一用时上较多会超时,方法二相对用时少一些。 算法复杂度分析: 法一时间复杂度为T(n)=O(n2), 法二时间复杂度为T(n)=O(n) 所以,法二更优!,核心代码,for(i=1;i=n;i+) scanf(“%d“, / 用数组 t i 存前 i 项的和。 ,算法的优缺点分析和改进,优点: 方法简单易懂,条理清晰 改进: 还有一部分人用树状数组,时间复杂度为O(nlgn) 总结: 拿到题目,先分析,各种情况都要考虑到位,可以简单化的问题尽量简单化。,谢谢观看!,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 区间 aneasyproblem4
链接地址:https://www.31doc.com/p-2596758.html