知识卡片
并集合并先复制再排除交叠
本实现先把set1的全部成员地址放入结果的新节点,再遍历set2。对于set2中的每一项,实际代码调用set_is_member(set1,该项),仅在set1没有它时加入结果。判重对象是原来的set1,不是逐渐变大的输出集合。
这依赖两个输入各自已是不含重复的集合,而且使用一致的相等规则。复制步骤可直接用底层尾插,因为这一阶段已知不会在结果中产生重复;若改用set_insert,就会再做一遍不必要的查重。
设输入大小为m、n,常数判等和节点插入模型下,上界可写O(m+n+mn),包含复制、外层遍历与成员扫描。两者非空时通常简记O(mn);若某边为空,不能由乘积为零误认为整个函数无需扫描或构造结果。
117指出并/交/差已保证结果中成员唯一,因此使用底层list_ins_next避免set_insert冗余扫描;它不是允许任意调用者破坏集合唯一性。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 并集合并先复制再排除交叠
- · 问与答
原书出处 · 2 处
- · 查看原书依据
遍历set1中的每个成员并把它们插入setu中,这个过程的时间复杂度为O(m)级的。在第二个循环中需要遍历set 2的每个成员,这使得这个循环的时间复杂度为处理set 2成员的操作的n倍。而这个循环需要包含时间复杂度为O(m)的set_is_member。因此,第二次循环的总体复杂度为O(mn)。由
- · 查看原书依据
set_insert的复杂度是O(n),因为它需要遍历集合中的元素以确保待插入的成员没有在集合中出现过。而set_union、set_intersection以及set_difference操作都已经确保了这一点,因此显然应该采用更高效的O(1)复杂度的list_ins_next来完成。 问:假设有
参考来源
- 位置:《算法精解:C语言描述》第7章《set_union》(spine1256;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1223.html;u109-ch07-015)。
- 结论依据:109全文及02793–02794并集完整函数实读,特别核对set_is_member(set1,...)的实际参数,保留空输入时线性工作;未执行。
- 原始内容:遍历set1中的每个成员并把它们插入setu中,这个过程的时间复杂度为O(m)级的。在第二个循环中需要遍历set 2的每个成员,这使得这个循环的时间复杂度为处理set 2成员的操作的n倍。而这个循环需要包含时间复杂度为O(m)的set_is_member。因此,第二次循环的总体复杂度为O(mn)。由
- 位置:《算法精解:C语言描述》第7章《问与答》(spine1264;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1231.html;u117-ch07-015)。
- 结论依据:117指出并/交/差已保证结果中成员唯一,因此使用底层list_ins_next避免set_insert冗余扫描;它不是允许任意调用者破坏集合唯一性。
- 原始内容:set_insert的复杂度是O(n),因为它需要遍历集合中的元素以确保待插入的成员没有在集合中出现过。而set_union、set_intersection以及set_difference操作都已经确保了这一点,因此显然应该采用更高效的O(1)复杂度的list_ins_next来完成。 问:假设有