求问luoguSCP-S初赛模拟赛17题
  • 板块题目总版
  • 楼主liyixin0514
  • 当前回复8
  • 已保存回复11
  • 发布时间2024/9/19 19:11
  • 上次更新2024/9/19 20:48:34
查看原帖
求问luoguSCP-S初赛模拟赛17题
542128
liyixin0514楼主2024/9/19 19:11
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))O(\min(p,q)\log (p+q)) 吗,但是因为 p+q2max(p,q)p+q\le 2\max(p,q),忽略常数 22 复杂度就一样了。求解答 \bx

2024/9/19 19:11
加载中...