网页
资讯
视频
图片
知道
文库
贴吧
地图
采购
进入贴吧
全吧搜索
吧内搜索
搜贴
搜人
进吧
搜标签
日
一
二
三
四
五
六
签到排名:今日本吧第
个签到,
本吧因你更精彩,明天继续来努力!
本吧签到人数:0
一键签到
成为超级会员,使用一键签到
一键签到
本月漏签
0
次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行
补签
。
连续签到:
天 累计签到:
天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
10月09日
漏签
0
天
python吧
关注:
466,290
贴子:
1,943,036
看贴
图片
吧主推荐
视频
游戏
首页
上一页
1
2
22
回复贴,共
2
页
,跳到
页
确定
<<返回python吧
>0< 加载中...
回复:算法(python版本) --- 持续更新
只看楼主
收藏
回复
拎壶冲
进士
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
仔细观察程序设计语言的特性,可以发现,除了与计算资源无关的定义语句之外(如c语言中的int a),主要就是三种控制流语言和赋值语句。而控制流仅仅起到了组织语句的作用,而不实施处理(计算机最基本的处理就是计算和存储嘛),但是一条赋值语句同时包含了(表达式)计算和变量(存储)两个基本资源。
所以,赋值语句是一个合适的选择。赋值语句运行的次数多,运行时间就长。反之亦然。
拎壶冲
进士
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
再回头看之前的累计求和问题,分析一下赋值语句执行的次数
第2行执行了一次赋值语句,第4行会执行n次赋值语句,所以赋值语句数量T(n)=1+n
汕头市万帮小能手生活服务
python
3.6.6/3.7/3.8/3.9 一键下载安装,无捆绑软件,安全无毒,适合小白,入门新手。赠送视频教程, 安装,人工客服在线解决您的所有问题
2024-10-09 20:35
广告
立即查看
拎壶冲
进士
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
知识点1:问题规模
问题规模是影响算法执行时间的主要因素
在这个例子里面,在前n个整数累计求和的算法中,需要累计的整数个数合适作为问题规模的指标。前10万个整数求和对比前1000个整数求和,是同一问题的更大规模。
知识点2:数量级函数
其实基本操作数量(前面所提到的赋值语句执行次数)函数T(n)的精确值并不是很重要,重要的是T(n)中起决定性因素的主导部分。这里我们需要用动态的眼光去看,就是当问题规模增大的时候,T(n)中的一些部分会盖过其他部分的贡献。以上例来说,T(n)=1+n,n就是这里的问题规模了,当n增大,这个常数1就不会很重要了。
数量级函数描述了T(n)中随n增加而增加速度最快的主导部分。称作“大O”表示法,记作P(f(n)),其中f(n)表示T(n)中的主导部分。
上面例子中的,T(n)=1+n,当n增大时,常数1在最终结果中就显得越来越无足轻重。所以可以去掉1,保留n作为主要部分,运行时间数量级就是O(n)。
拎壶冲
进士
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
练习:
当n很小时,比如n=1,常数1000起决定性作用。但当n越来越大,n平方项就越来越重要,其他两项对结果的影响则越来越小。同样的,n平方项的系数5,对于n平方的增长速度来说也影响不大。所以可以在数量级中去掉10n+1000,以及系数5。
确定运行时间数量级为
拎壶冲
进士
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
常见的大O数量级函数:
拎壶冲
进士
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
影响算法运行时间的其他因素:
有时候决定运行时间的不仅是问题规模,某些具体数据也会影响算法运行时间。比如说排序,一个是一堆杂乱无章的数进行排序和一个几乎接近已经排序好了的进行排序,执行的赋值语句的数量也会不一样,算法运行的时间也会不一样。所以,我们也会把算法的执行时间分为最好、最差、平均情况,其中平均状况体现了算法的主流性能。对算法的分析要看主流,而不被某几种特定的运行状态所迷惑。
拎壶冲
进士
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
最后再说下,其实除了有大O表示法,还有大Ω表示法,大θ表示法。没必要去研究啊,知道还有这么个东西就行了。
拎壶冲
进士
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
练习题:从代码分析确定执行时间数量级函数
登录百度账号
扫二维码下载贴吧客户端
下载贴吧APP
看高清直播、视频!
贴吧页面意见反馈
违规贴吧举报反馈通道
贴吧违规信息处理公示