求问luoguSCP-S初赛模拟赛17题

liyixin0514 @ 2024-09-19 19:11:41

set <int> intersection(set <int> a, set <int> b) {
    if (a.size() > b.size()) swap(a, b);
    set <int> res = a;
    for (int i : a)
        if (b.count(i) == 0)
            res.erase(i);
    return res;
}

by liyixin0514 @ 2024-09-19 19:15:13

17. 设集合 a,b 的元素个数分别为 p,q，则执行函数 intersection(a,b) 的时间复杂度为

by truly_handsome @ 2024-09-19 19:28:27

@cjh20090318 set 遍历不是 O(n) 的吗。

by SnowTrace @ 2024-09-19 19:29:06

@cjh20090318 这个东西不是 1log 的吗，应该把遍历和删除复杂度加起来吧，复杂度 O(\operatorname {min}(|p|,|q|)\log(|p||q|))

by cmk666 @ 2024-09-19 19:31:55

@cjh20090318 单次最坏是 O(\log n) 但是总和是 O(n) 的啊

by SnowTrace @ 2024-09-19 19:32:40

我查了一下遍历确实是线性的啊，根本不用管遍历这一块，循环里面干的事情是给 a 删数和在 b 里面查数，分析出来就上面那个复杂度

by liyixin0514 @ 2024-09-19 19:52:45

@yh2021tanghao @cmk666 @SnowTrace 我没查到，但是我试了一下，遍历看起来不像线性，像单 log。测试代码如下：

#include<bits/stdc++.h>
//#define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
set<int> st;
const int N=5e6;
mt19937 rd(time(0));
void work1(){
    clock_t s=clock();
    int a=0;
    rep(i,1,N) a+=rd(); 
    pf("%d\ntime1 is %lfs.\n",a,1.0*(clock()-s)/CLOCKS_PER_SEC);
}
void work2() {
    rep(i,1,N) st.insert(rd());
    clock_t s=clock();
    int a=0;
    for(auto u:st) {
        a+=u;
    }
    pf("%d\ntime2 is %lfs.\n",a,1.0*(clock()-s)/CLOCKS_PER_SEC);
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("my.out","w",stdout);
    #endif
    work1();
    work2();
}

by truly_handsome @ 2024-09-19 20:00:41

@liyixin0514 18 行 insert 是带 log 的

by liyixin0514 @ 2024-09-19 20:01:48

@yh2021tanghao

我是在 insert 后面才开始计时的。

by SnowTrace @ 2024-09-20 22:45:51

@liyixin0514 我刚刚才把这张卷子做了一遍，好像其实不是这里的问题，你注意到上面的复杂度没有和 max(p,q) 有关系，而实际上你把两个集合都传进函数里复杂度已经是 O(p+q) 的了，就考虑 min(p,q) 很小， max(p,q) 很大的时候上面那个分析就错了。

by liyixin0514 @ 2024-09-21 18:13:04

@SnowTrace 原来传参传 set 是 O(n) 的吗，请问是所有 STL 传参都是这个复杂度吗，网上没搜到。我试了一下，好像是这样，不过换成引用或指针好像就可以跑得飞快。常识又增加了