最新要闻
- 800W功耗!RTX 4090 Ti四插槽"核弹"真的有 但不一定能生出来
- 全球微速讯:《最后生还者》剧集第3集与游戏对比 还原度高
- 实时焦点:摩托骑手广东高速上恶意损坏其他车辆 官方回应:一刀切禁摩很好?
- 每日短讯:12.4万买新帕纳梅拉!近600名国内网友保时捷官网疯抢:成功下单后被取消
- 【全球时快讯】奔驰获全球首家L3级自动驾驶认证:开车不用看路 出事故奔驰负责
- 【快播报】优酷回应1元会员被扣24元争议:活动规则已告知 扣钱没毛病
- 当前热文:水墨风场景惊艳!《仙剑奇侠传7》DLC《人间如梦》官宣2月发售
- 彻底扑灭一台特斯拉Model S有多难 消防员实测:用了22.7吨水
- 【环球播资讯】小鹏股价暴跌、交付量惨淡 何小鹏专访回应:未来会这么做
- 全球动态:全球首个!婴幼儿视功能损伤手机智能筛查系统面世
- 撸猫手感 绿联iPhone 12-14系列液态硅胶保护壳9.9元起
- 天天快看点丨海淘不香了!日版Xbox主机涨价将近260元
- 天天速递!全国首烧?疑似红旗E-HS9充电时起火 现场黑烟弥漫
- 瑾娘为什么要杀华裳?瑾娘为什么假扮巽芳?
- 爱在旅途大结局是什么?爱在旅途剧情介绍
- 法国属于西欧还是北欧?南欧包括哪些国家?
广告
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
c++代码实现中时间复杂度的不断优化
(相关资料图)
先来介绍一下时间复杂度:
同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。
时间复杂度的优化通常在暴力枚举中尤为重要,或许O(n*n)会得零分但是O(n*logn)可以得满分,所以在编写程序过程中我们要优先考虑时间较短的算法(洛谷里最绝望的就是看到TLE,这意味着代码要重新编写)。总之有快方法用上绝对没问题,除非NOIP时间不够可以快速写一段骗(拿)一些分数。
下面以洛谷P2241 统计方形(数据加强版)为例讲解一下具体如何不断优化程序的时间复杂度:
例10.1 (洛谷 P2241, NOIP1997 普及组 加强)
有一个 n×m(n, m ≤ 5000) 的棋盘,求其方格包含多少个(四边平 行于坐标轴的)正方形和长方形。
本题中, 长方形中不包括正方形。
样例解释: 如图,正方形一共 8 个,长方形 10 个 正方形中,边长为 1 的 6 个,边长为 2 的 2 个;
长方形中, 1 ×2 的 4 个, 1 ×3 的 2 个, 2 × 1 的 3 个, 2 ×3 的 1个。
思路1:用四重循环,直接枚举 4 个参数,即两横边两竖边:
通过左上角和右下角的顶点进行枚举,如果长度相等就是正方形,否则就是长方形。
所以,这样可以保证不重复地遍历所有的方形。
根据循环的范围可知,我们也没有遗漏任何的方形。
时间复杂度O(n2 m2 ) ……似乎有点慢。
但是至少, 答案正确了。
1 //枚举左上、右下顶点 时间复杂度O(n^2*m^2) 2 #include3 using namespace std; 4 typedef long long LL; //LL是已经定义好的long long 5 int main(){ 6 int n,m; 7 LL squ=0,rec=0;//squ统计正方形个数,rec统计长方形个数 8 cin>>n>>m; 9 for(int x1=0;x1 为什么是 x2 从 x1+1 开始, y2 从 y1+1 开始枚举?
• 如果 x1 > x2, 那么 x1 就不再是左侧了, x2 才是左侧 (左图)
• 如果 x1 = x2, 那么无法构成长方形, 退化为一根线段 (中图)(就是那根消失的线段)
• 只有 x1 < x2, 才能正常构成长方形(右图)。
y1 、y2 同理
思路 2: 以下左图中的点 (3, 4)为例(左下角为原点)。
位于同一对角线 (图中虚线)上所有点均可构成正方形。
除自身所在行列外,所有其它点均可与其构成长方形;故直接得 长方形数为 nm – 正方形数。
从右图可以看出, 每一个长/正方形均被其 4 个顶点各计算一次。 因此,最终答案需要除以 4。
斜线上的格点个数为多少呢?
若顶点在长方形顶点,格点个数为长方形的短边长,即 min(n,m)。
否则,以顶点为界分为4份 。
每份都这样计算,得到正方形个数: min x, y + min n − x, y + min x, m − y + min(n − x, m − y)
因此, 枚举(x, y)后,可在 O(1) 时间内计算答案,求和。 总时间复杂度 O(nm),直接优化掉一个 O(nm)
1 //枚举一个点构成的所有矩形,统计结果除4 时间复杂度O(n*m) 2 #include3 using namespace std; 4 typedef long long LL; //LL是已经定义好的long long 5 int main(){ 6 int n,m; 7 LL squ=0,rec=0; 8 cin>>n>>m; 9 for(int x=0;x<=n;x++)10 for(int y=0;y<=m;y++){11 LL tmp=min(x,y)+min(n-x,y)+min(x,m-y)+min(n-x,m-y);//对角线的正方形枚举方式 12 squ+=tmp;13 rec+=n*m-tmp;14 }15 cout< 还能不能更快呢?
思路 3:每一个长方形重复了4次。能否不重复呢?
结合思路 1可知, 只需考虑右上角为 (x, y) 的情况,因此计算斜线 上的顶点时, 只需要向左下角一个方向拓展!
(先算 4 个方向, 再除以 4,可谓是画蛇添足啊…… )
1 //枚举右下角顶点 时间复杂度O(n*m) 2 #include3 using namespace std; 4 typedef long long LL; 5 int main(){ 6 int n,m; 7 LL squ=0,rec=0; 8 cin>>n>>m; 9 for(int x=0;x<=n;x++)10 for(int y=0;y<=m;y++){11 LL tmp=min(x,y);12 squ+=tmp;13 rec+=x*y-tmp;14 }15 cout< 当然,这里选择固定其它角也是等价的,但是固定右上角最简单。
注意:这里的原点是在左下角, 列是 x,行是 y。
如果选择左上角 作为原点, 那么枚举的就是长方形右下角。
思路4:枚举边长 (a, b)。题目变为在 n × m 的长方形中能放置多少 个 a×b 的方形。
注意 a 、b 有序, a×b 和 b×a 不等价。
• n 列中选连续 a 列:[1,a],[2,a+1], … ,[n-a+1,n],共 n-a+1 种可能。
• m 行中选连续 b 行构成方形, 同理有 m-b+1 种情况。 所以 n × m 的长方形中可容纳 (n-a+1)×(m-b+1) 个 a×b 的矩形。
对于边长 k, 只有长等于宽, 才能构成正方形;其余均为长方形。
如果 a=b, 就计入正方形。 使用循环枚举 a 、b, 累加求和即可
1 //枚举两条边 时间复杂度O(n*m) 2 #include3 using namespace std; 4 typedef long long LL; 5 int main(){ 6 int n,m; 7 LL squ=0,rec=0; 8 cin>>n>>m; 9 for(int a=1;a<=n;a++)10 for(int b=1;b<=m;b++) 11 if(a==b)12 squ+=(n-a+1)*(m-b+1);13 else14 rec+=(n-a+1)*(m-b+1);15 cout< 还可以再快!!!
思路 5:沿用刚才乘法原理的思想,枚举量还可进一步减少?
在 n × m 的长方形中的矩形个数, 等价于在 m+1 条行线中选首尾 2 行、在 n+1 条列线中选首尾 2 列所围成的方形数目!
在 n+1 列中选 2 列线围长方形,左列 n+1 种情况 ;右线列不能和 左列线重复, 只有 n 种情况,将他们乘起来。
由于重复统计 (左右和右左),要除以2,有 1/2n(n + 1) 种可能。 同理,行有 1/2m(m + 1) 种可能。一共1/4 m(m + 1) n (n+1)矩形。
借助思路4, 去掉其中的正方形。时间复杂度降到 O(min(m, n))。
1 //枚举一条边 时间复杂度:O(n) 2 #include3 using namespace std; 4 typedef long long LL; 5 int main(){ 6 int n,m; 7 LL squ=0,rec=0; 8 cin>>n>>m; 9 for(int a=1;a<=min(n,m);a++)10 squ+=(n-a+1)*(m-a+1);11 rec=(n+1)*n*(m+1)*m/4-squ;12 cout< 写出这样的代码还需要担心不能AC吗?
完结撒花!!!
码字不易,点个赞再走吧。
关键词: 时间复杂度
聚焦:一步一步实现若依框架--2.4数据权限 data_scope
1、点击若依的系统用户管理页面,测试各种数据权限生成的sql,若依调用的后台方法是:@DataScope(deptAl...
来源: c++代码实现中时间复杂度的不断优化
聚焦:一步一步实现若依框架--2.4数据权限 data_scope
800W功耗!RTX 4090 Ti四插槽"核弹"真的有 但不一定能生出来
全球微速讯:《最后生还者》剧集第3集与游戏对比 还原度高
实时焦点:摩托骑手广东高速上恶意损坏其他车辆 官方回应:一刀切禁摩很好?
天天观察:云萌 V2.6.3.0 win10,win11 Windows永久激活工具
热推荐:基于Spring Cache实现Caffeine、jimDB多级缓存实战
portswigger 靶场之 XSS 篇 (下)
全球最新:【算法训练营day32】LeetCode122. 买卖股票的最佳时机II LeetCode55. 跳跃游戏 LeetCode45. 跳跃游戏II
部署Kubernetes Cluster
每日短讯:12.4万买新帕纳梅拉!近600名国内网友保时捷官网疯抢:成功下单后被取消
【全球时快讯】奔驰获全球首家L3级自动驾驶认证:开车不用看路 出事故奔驰负责
【快播报】优酷回应1元会员被扣24元争议:活动规则已告知 扣钱没毛病
当前热文:水墨风场景惊艳!《仙剑奇侠传7》DLC《人间如梦》官宣2月发售
彻底扑灭一台特斯拉Model S有多难 消防员实测:用了22.7吨水
天天快消息!Android 软键盘丝滑切换(一)
天天看点:视频发布失败原因不好找?火山引擎数智平台这款产品能帮忙
速看:OpenYurt v1.2 新版本深度解读(一): 聚焦边云网络优化
【环球播资讯】小鹏股价暴跌、交付量惨淡 何小鹏专访回应:未来会这么做
全球动态:全球首个!婴幼儿视功能损伤手机智能筛查系统面世
撸猫手感 绿联iPhone 12-14系列液态硅胶保护壳9.9元起
天天快看点丨海淘不香了!日版Xbox主机涨价将近260元
天天速递!全国首烧?疑似红旗E-HS9充电时起火 现场黑烟弥漫
瑾娘为什么要杀华裳?瑾娘为什么假扮巽芳?
爱在旅途大结局是什么?爱在旅途剧情介绍
法国属于西欧还是北欧?南欧包括哪些国家?
荷兰为什么被称为水之国?荷兰水之国的资料简介
长宽高的英文缩写分别是什么?长宽高怎么算平方?
oppor7手机版本低怎么升级?oppo r7手机参数
复工第一天:请马上卸载这个恶心的软件!!!
全球看热讯:python-paramiko操作的封装
无法定位序数是什么意思?无法定位序数怎么解决?
打印机驱动在电脑哪里找?如何卸载打印机驱动?
无线适配器或访问点有问题是什么意思?无线适配器或访问点有问题怎么处理?
魅族手机怎么样?魅族手机锁屏密码忘了怎么解开?
环球速讯:工信部明天起优化调整微波频率 为5G/6G预留频谱资源
【独家】美国下手真狠!沃尔沃在美被罚8.7亿元 史上最大
快消息!APP竟比线下贵一倍还多 有电影院劝说观众退订淘票票
【世界快播报】提车1周 一特斯拉高速上行驶时方向盘脱落:维修还被收费
每日速读!全球最大游戏展E3辉煌不在:微软索尼任天堂“御三家”将集体缺席
波司登云原生微服务治理探索
今日热门!元宵节将至!元宵夜将出现年度最小满月
世界实时:侄子出演叔叔 MJ传记片年内开拍
【速看料】女子抱娃人肉占车位 还移走路障为自家车开路 结局引人舒适
世界讯息:西安阿房宫站将更名西安西站:原西站不够西
天天观热点:猪肉含量≥85% 一口全是肉:亚明猪肉烤肠2斤29.9元大促
焦点要闻:读Java8函数式编程笔记06_Lambda表达式编写并发程序
【全球新要闻】全网影视免费看,最新电影、电视剧免广告免VIP观看,只要你能搜到的,统统都能看,《狂飙》、《三体》追剧神器,时刻掌握最新剧集,无需安装,使用简单,
被苹果踢出供应链两年了 欧菲光仍未缓过劲:2022巨亏40多亿
精选!疯狂玩梗!强盛集团孙红雷直播被买鱼刷屏
焦点短讯!A卡很难追 游戏开发者越来越喜欢DLSS:理由离谱 弥补D加密损失
环球即时看!2023春节档爆发:复苏满座与极端的粉黑大战
每日消息!关于桌面上一万多个图标
刘慈欣:30年前拍不成《流浪地球2》 投资人不信中国有太空电梯
世界快看:老外幸福感暴降:英国近半年轻人担心收入永远不够养家
别贪速度快!SSD选什么接口更适合你?
《敢死队2》观后感
环球快报:VUEX 使用学习六 : modules
国产奋起!26557款软件力挺飞腾CPU
最新资讯:三大航空公司2022年合计预亏逾1000亿元!三大因素、东航最惨
环球观察:三亚凤凰机场出现滚滚浓烟?机场回应:暂无影响
快消息!这次过年 网吧终于活过来了!和以前完全不一样
河南矿山回应3名员工各领500万奖金:有人销售额超3亿
【环球报资讯】每个前端程序员都应该知道的10个Chrome扩展
刘慈欣:电影《流浪地球2》是原创而非小说改编 全方位超越第一部
今日聚焦!广东一男子打球6天后发现头顶卡对手2颗牙:网友神评论
焦点热议:索尼真有你的:背后给微软捅刀子
Acw 170.加成序列
精彩看点:React组件的使用
【全球独家】理想L5车型首次公布:不是SUV 价格坚守20万以上
每日热讯!最新显卡天梯榜公布:前十NVIDIA占五席!RTX 4090断层第一
全球新动态:杭州岳庙秦桧像被砸烂9次 游客仍不解气:专家称泄愤不应暴力
世界资讯:腾讯游戏春节7天吸金超4.5亿:《王者荣耀》独占一半 稳坐第一
世界信息:一加平板来了:Star Orbit金属打造 CNC一体机身
佳能2022年营收破4万亿日元 相机收入暴增 完全不惧手机蚕食
画面有点上头!男子扛铁板狂砸秦桧雕像:《满江红》带火景区热度
赚了!科学家在南极发现罕见大陨石:7.7公斤
全球消息!【Python】爬虫实战-基于代理池的高并发爬虫
焦点快看:rust写一个im聊天服务
全球看点:打破日本垄断!OLED关键材料FMM首次国产
环球今日讯!R星今日正式入驻B站!网友“花式”催更《GTA6》
全球观天下!显卡、主板返修排行:戴尔居然完美第一!AMD极度尴尬
环球简讯:神舟十五号航天员准备首次出舱!期待“感觉良好”
天天资讯:真我GT Neo5明天官宣 网友:赢麻了
每日视点!国产PCIe 4.0硬盘天花板 致态TiPro7000 1TB到手699元
《流浪地球2》热映 张朝阳称引力弹弓真实存在:美国航天器经历过
全球视点!比亚迪2022年业绩预告出炉:净利润同比暴增超450%
世界今热点:65寸电视不到2000元 LCD跌成白菜价 面板一哥京东方2022利润大跌70%
荣耀Magic5系列定档:2月27日MWC巴塞罗那见
Java中23种设计模式介绍和应用场景总结
今头条!手机测试之-adb
环球时讯:《鹅鸭杀》爆火,一文带你了解如何实现顶流社交游戏
DevOps: 自动与手动部署语义化版本(Semantic Versioning)实操
焦点信息:手上有了这些工具,明天争取6点下班了!
全球焦点!平价神器!新iPad mini 7曝光:处理器/屏幕惊喜
女子买电影票发现仅一个普通座位 其他全是C位 工作人员也无语
每日短讯:他真的很忙!雷军站公司门口给小米员工挨个发红包
最资讯丨打工人热议今天怎么才是周一:专家科普节后综合征
【全球热闻】《无名》折戟春节档:4.9亿票房只排第4、粉黑大战尴尬
springboot整合activiti实现流程审批(支持单体、微服务融合)