求助qwq,AC后想问问dalao们关于此题时间复杂度的问题

P1983 [NOIP2013 普及组] 车站分级

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是O(1)的,如果if里面也是O(1)的复杂度就是O(n),否则就是O(if为true的次数*if里面语句的复杂度+n)

感性地理解一下就好了


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
复杂度不算,但是实测效率是要算的
不得不扯O()的定义了

g(x)=O(f(x))$表示存在一个$c$,使得$x→∞, g(x)\leq cf(x)

所以计算复杂度g(x)的时候会把常数去掉
但看实测效率的时候,比如说你有一个O(n)算法,自带一个10^{18}的常数,你还是跑不过去
所以实测效率是跟常数有关的,常数大可能会让你过不了理论复杂度能过的,常数小可能会让你过理论复杂度很危的


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的严格来说是错解,但是因为数据水卡过去了

正解应该是中间建个虚点

时间复杂度挺简单的吧,多做点题就懂得分析了


上一页 | 下一页