首页IT科技以下c语言函数时间复杂度是(c++代码实现中时间复杂度的不断优化)

以下c语言函数时间复杂度是(c++代码实现中时间复杂度的不断优化)

时间2025-08-01 17:34:44分类IT科技浏览5366
导读:先来介绍一下时间复杂度: 同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。...

先来介绍一下时间复杂度:

同一问题可用不同算法解决               ,而一个算法的质量优劣将影响到算法乃至程序的效率               。算法分析的目的在于选择合适算法和改进算法                      。

计算机科学中                      ,算法的时间复杂度是一个函数       ,它定量描述了该算法的运行时间       。这是一个关于代表算法输入值的字符串的长度的函数               。时间复杂度常用大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 ) ……似乎有点慢                      。

但是至少                      , 答案正确了。

为什么是 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 #include<bits/stdc++.h> 3 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<<squ/4<<" "<<rec/4<<endl;//四个顶点算了四次                      ,所以要除4输出 16 return 0; 17 }

还能不能更快呢?

思路 3:每一个长方形重复了4次       。能否不重复呢?

结合思路 1可知       , 只需考虑右上角为 (x, y) 的情况               ,因此计算斜线 上的顶点时                      , 只需要向左下角一个方向拓展!

(先算 4 个方向       , 再除以 4        ,可谓是画蛇添足啊…… )

1 //枚举右下角顶点 时间复杂度O(n*m) 2 #include<bits/stdc++.h> 3 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<<squ<<" "<<rec<<endl; 16 return 0; 17 }

当然                      ,这里选择固定其它角也是等价的               ,但是固定右上角最简单                      。

注意:这里的原点是在左下角        , 列是 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 #include<bits/stdc++.h> 3 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 else 14 rec+=(n-a+1)*(m-b+1); 15 cout<<squ<<" "<<rec<<endl; 16 return 0; 17 }

还可以再快!!!

思路 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 #include<bits/stdc++.h> 3 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<<squ<<" "<<rec<<endl; 13 return 0; 14 }

写出这样的代码还需要担心不能AC吗?

完结撒花!!!

码字不易,点个赞再走吧               。

声明:本站所有文章                      ,如无特殊说明或标注                      ,均为本站原创发布。任何个人或组织,在未征得本站同意时               ,禁止复制                       、盗用       、采集       、发布本站内容到任何网站                       、书籍等各类媒体平台                      。如若本站内容侵犯了原著者的合法权益                      ,可联系我们进行处理                      。

创心域SEO版权声明:以上内容作者已申请原创保护,未经允许不得转载,侵权必究!授权事宜、对本内容有异议或投诉,敬请联系网站管理员,我们将尽快回复您,谢谢合作!

展开全文READ MORE
啥时候才有网(什么时候网创-网络赚钱:凡人修假,借假修真) 如何在电子商务平台做好企业网站的推广运营(如何在电子商务平台上做好企业网站的推广)