求问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;
}
  1. 设集合 a,b 的元素个数分别为 p,q,则执行函数 intersection(a,b)的时间复杂度为 Θ(min(?, ?) log max(?, ?))。( )

答案是 F,请问正确的复杂度是什么。我认为是 O(\min(p,q)\log (p+q)) 吗,但是因为 p+q\le 2\max(p,q),忽略常数 2 复杂度就一样了。求解答 \bx


by SnowTrace @ 2024-09-21 19:15:54

@liyixin0514 不大懂啊,直接传进去就相当于把这一整个容器都复制一遍到函数里面吧,大概都是线性的


by liyixin0514 @ 2024-09-21 21:24:50

@SnowTrace 拜谢orz,应该没什么问题了,此帖结。


上一页 |