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 expect @ 2020-12-16 20:17:18
@aldol_reaction 判断是否exit是
感性地理解一下就好了
by expect @ 2020-12-16 20:19:30
但是假如if里面的复杂度比n大很多导致那个n没啥影响很多人也不会把n写进复杂度里
by aldol_reaction @ 2020-12-16 20:21:04
@w23c3c3 其实不太应该纠结这个地方...但是这个题如果是按照您说的话,是不是应该算O(nnm)呢?其实我的问题就是。
当一个机子能跑1e8的时候,我判断我会不会TLE的标准是看时间复杂度能不能超过1e8还是乘上常数判断呢?因为常数大小在临界范围还是挺重要的吧?
and如果1s能跑1e8的话,我能跑过最大的范围是1e9吗?
不好意思我有点啰嗦了,这个题一开始不敢写O(nnm)复杂度的导致我卡了三个半小时。
by aldol_reaction @ 2020-12-16 20:26:06
蒟蒻好像明白了@千反田 话说一个exit条件怎么能不是O(1)呢不就常数个语句判断嘛
by expect @ 2020-12-16 20:26:57
@aldol_reaction 你写个O(n)的函数判断也是有可能的(
by aldol_reaction @ 2020-12-16 20:27:03
rxz说2e7稳我丢
by w23c3c3 @ 2020-12-16 20:28:36
@aldol_reaction
复杂度不算,但是实测效率是要算的
不得不扯
所以计算复杂度
但看实测效率的时候,比如说你有一个
所以实测效率是跟常数有关的,常数大可能会让你过不了理论复杂度能过的,常数小可能会让你过理论复杂度很危的
by expect @ 2020-12-16 20:30:36
@aldol_reaction
指ccf少爷机
by aldol_reaction @ 2020-12-16 20:32:02
多谢二位dalao的详细解答qwq(好感动).还是我太蒟蒻了。最后再弱弱问一下,时间复杂度这方面需要看书恶补吗,有书推荐嘛。算法导论是不是太难了qwq.~您们刚刚分析的那些时间复杂度,我还真不知道~~
by expect @ 2020-12-16 20:34:38
@aldol_reaction 草我刚才说错了是5e7和1e8
你那个n^2m的严格来说是错解,但是因为数据水卡过去了
正解应该是中间建个虚点
时间复杂度挺简单的吧,多做点题就懂得分析了