知识卡片
交差集按另一集合筛选
本实现的交集与差集都遍历set1,并为每一项查询它是否属于set2。交集复制匹配项的数据地址,差集复制不匹配项的数据地址,结果各有新链表节点。
两种操作只改变保留条件,因此可用同一“遍历候选—查询另一集合—按条件保留”的思路理解。差集不能随意对调输入;即使数学交集对称,本实现也固定从第一个输入借用数据地址,调换输入可能改变具体代表对象及执行成本。
设大小m、n,常数判等和分配模型下,上界为O(1+m+mn),包含外层扫描;n=0时仍会扫描set1。无须把每次已知不会重复的结果插入再次交给set_insert查重。
111及02795 set_difference:遍历set1,若set_is_member(set2,…)为真就continue,否则尾插结果。输入不调换,借用对象来自set1,分配失败仍只清理输出节点。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
set_intersection set_intersection操作将建立一个集合,记为seti。这是由参数set1和set2所指定集合的交集结果(见示例7-2)。首先,调用set_init来初始化seti,然后针对set1中的每一个成员调用set_is_member来确定set1中的成员是否在s
- · 查看原书依据
如果没有出现过,则将该成员插入setd中。 set_difference的时间复杂度为O(mn)级的,这里m和n分别代表集合set1和set2中的成员个数。这是因为,针对set1中的每一个成员都需要执行复杂度为O(n)的set_is_member操作以此来确定该成员是否也在集合set2中出现过。
参考来源
- 位置:《算法精解:C语言描述》第7章《set_intersection》(spine1257;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1224.html;u110-ch07-016)。
- 结论依据:110全文与02794交集代码实读,111全文及02795差集代码实读;明确迭代输入、成员判断正反分支、借用对象和直接list_ins_next。
- 原始内容:set_intersection set_intersection操作将建立一个集合,记为seti。这是由参数set1和set2所指定集合的交集结果(见示例7-2)。首先,调用set_init来初始化seti,然后针对set1中的每一个成员调用set_is_member来确定set1中的成员是否在s
- 位置:《算法精解:C语言描述》第7章《set_difference》(spine1258;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1225.html;u111-ch07-016)。
- 结论依据:111及02795 set_difference:遍历set1,若set_is_member(set2,...)为真就continue,否则尾插结果。输入不调换,借用对象来自set1,分配失败仍只清理输出节点。
- 原始内容:如果没有出现过,则将该成员插入setd中。 set_difference的时间复杂度为O(mn)级的,这里m和n分别代表集合set1和set2中的成员个数。这是因为,针对set1中的每一个成员都需要执行复杂度为O(n)的set_is_member操作以此来确定该成员是否也在集合set2中出现过。