aldol_reaction @ 2020-12-16 19:48:50
蒟蒻建图的AC代码片段在最后面。 我没开O2,用的vector存边,827msAC。但是此题复杂度是O(nnm),1e9是怎么卡过1s的?我记得1s时间复杂度两千万是可以过的。
还有个问题是,常数优化的数量级范围是多少呢。
还有想问一下我一直不懂的地方
for(int j = start; j <= endd; ++j) {
if(stand_bool[j]) {
for(int k = start; k <= endd; ++k) {
if(!stand_bool[k] && !exit_edge[j][k]) {
++in[j], ++out[k];
e[k].push_back(j);
exit_edge[j][k] = 1;
}
这个AC代码片段.n个点至多n/2个停下来,n/2不停下来,这样乘起来时间复杂度最大。变成O(nnm/4)。但是每一次循环我都需要在if判断,这个if判断算不算在时间复杂度里面呢...算的话不就是O(nnm)了吗。(好蒟蒻的问题QAQ) 完整建图部分的AC代码
void inp() {
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
int s = 0;
scanf("%d", &s);
memset(stand_bool, 0, sizeof(stand_bool));
for(int j = 1; j <= s; ++j) {
scanf("%d", &stand_num);
stand_bool[stand_num] = 1;
if(j == 1) {
start = stand_num;
if(final_start > start) final_start = start;
}
if(j == s) {
endd = stand_num;
if(final_endd < endd) final_endd = endd;
}
}
for(int j = start; j <= endd; ++j) {
if(stand_bool[j]) {
for(int k = start; k <= endd; ++k) {
if(!stand_bool[k] && !exit_edge[j][k]) {
++in[j], ++out[k];
e[k].push_back(j);
exit_edge[j][k] = 1;
}
}
}
}
}
}
by w23c3c3 @ 2020-12-16 19:56:51
luogu现在的机子1s跑4e8不是问题,所以自带1/4常数的
by expect @ 2020-12-16 19:59:08
1.这题正解应该是nm的,因为nm^2大多数情况下跑不满所以过了
2.时间复杂度不算常数
by aldol_reaction @ 2020-12-16 20:06:42
@千反田 不知n=1000的时候,多少以内算常数呢?
by w23c3c3 @ 2020-12-16 20:09:25
常数在分析复杂度内都不记,但是实测效率需要考虑常数因子
有的比如说
by aldol_reaction @ 2020-12-16 20:10:36
楼上的两位dalao,本蒟蒻还想请教一下,一直有个问题就是。
for(int i = 1; i <= n; ++i){
if(exit){
do something;
}
}
这样一个for循环,只有exit条件成立才做do something。那么计算时间复杂度的时候,是只算满足exit条件的n的数量吗?但是不满足eixt的n也会进入循环先进入if语句判断,这个时间为什么不计算了呢?
by aldol_reaction @ 2020-12-16 20:13:15
@w23c3c3 emmmm我就是不太确定常数到底多大算常数,小于logn的就可以认为是常数了吗
by w23c3c3 @ 2020-12-16 20:13:18
其实应该是要算O(n)的
by expect @ 2020-12-16 20:14:02
@aldol_reaction
常数因子不写进时间复杂度,不管你的实际运行次数是
前者“常数大”,后者“常数小”,运行时间天差地别,但是时间复杂度是一样的
by expect @ 2020-12-16 20:14:54
@aldol_reaction 和题目输入数据无关的都不算进去
by aldol_reaction @ 2020-12-16 20:17:18
@千反田 常数这个地方蒟蒻终于懂了...太蒟蒻了,谢谢大佬qwq