C中if中连接的判断条件交换顺序之后耗时增大一倍多正常吗

2019-11-04 17:50:22

谢邀。首先希翼能改变你的一个观点，你所谓的“常数优化”是计算机科学中非常重要并且非常科学的部分，其应用价值远大于算法复杂度的优化，十大正规网投平台也是在离开OI界后才认识到这一点的。但就这个题目来说，你使用了邻接矩阵导致每次必须遍历完N*N条边，因此你的算法的复杂度是O(K*N*N)，而题目条件已经说明最多只有N*100条边，使用邻接表能优化到O(K*N*100)的复杂度。再看你的两种实现，其区别可以从三个方面分析，1)这个if判断会实行K*N*N次，因此它是算法的瓶颈，它的效率的会极大影响整个程序的运行时间。2)缓存机制(cache)。内存非常便宜但是慢，cache容量小但是速度快（与cpu速度相当），其速度差距上百倍（参考http://www.cs.cornell.edu/projects/ladis2009/talks/dean-keynote-ladis2009.pdf，感谢@高洋指正）。计算机虽然将数据放在内存中，但是访问内存中的数据时会将其相邻的区域载入到cache中，考虑到常见程序访问内存时都有较好的地址连续性，这么做可以非常有效的加快数据读写的速度。你的实现中，graph[i][node]是访问一个矩阵的一列，由于二维矩阵在内存中是行优先存储的，因此相邻两次访问相差1005*sizeof(int)个位置，完全无法利用上cache机制的优势。而flag[i]是一个完美的连续访问，所以很快。3)由于if的短路求值特性（在A&&B中如果A判断为false则不会判断B），graph[i][node]判断为false的概率为1-100/N，!flag[i]判断为false的概率为1/2，如果graph[i][node]与!flag[i]的实行时间一样的话确实应该将graph[i][node]放在前面会比较快，但由于2)中的分析，两者速度相差上百倍，所以自然把!flag[i]放在前面会更快，这就造成了你看到的结果。当然，这也只是一个粗略的分析，流水线和分支预测机制在这个例子中也会有一定的影响。这是十大正规网投平台刚刚实现的一个代码，可供参考，第五个测试点需时123ms。#include<iostream>#include<cstdio>#include<vector>usingnamespacestd;constintmaxn=1000+5;intN,L,K;intv[maxn],h[maxn];vector<int>e[maxn];intmain(){scanf("%d%d",&N,&L);for(inti=1;i<=N;++i){intx,y;scanf("%d",&x);while(x--){scanf("%d",&y);e[y].push_back(i);}}scanf("%d",&K);for(intk=1;k<=K;++k){intsrc;scanf("%d",&src);v[src]=k;h[src]=0;vector<int>q;q.push_back(src);for(inti=0;i<q.size();++i){intx=q[i];if(h[x]>=L)break;for(intj=0;j<e[x].size();++j){inty=e[x][j];if(v[y]!=k){v[y]=k;h[y]=h[x]+1;q.push_back(y);}}}printf("%d ",q.size()-1);}return0;}最后，十大正规网投平台是看到你定义常数的习惯和十大正规网投平台一样+5，所以才答这么认真的~不过还是不建议用[1005][1005]这样的写法~

上一条：上一篇：2018双十二有什么值得买或者一些应该了解的游戏规则
下一条：下一篇：JasonWhite是谁

相关产品

相关资讯