知识卡片
等价集合表达式成本可不同
同一成员关系可由不同操作组合表达:A⊆B当且仅当A∩B=A;A=B当且仅当A−B和B−A都为空;A∩B=A−(A−B)。这些等式使接口能相互组合,却不表示组合与专用函数成本相同。
专用子集查询可边扫描边发现反例,无须先分配交集节点;组合方案会构造临时集合并负责清理。在本章线性查询模型中,它们可能有相同渐近等级,但“约两倍”只是原书粗略成本说明,不是任意输入下的精确时间比例,提前退出、分配与常数都会影响结果。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
联合使用set_intersection和set_is_equal操作来达成相同的目的。无论我们按照本章给出的实现方式还是联合使用set_intersection和set_is_equal,它们的时间复杂度都是O(mn),这里m和n分别代表集合S1和S2的成员个数。但是,如果调用set_inters
参考来源
- 位置:《算法精解:C语言描述》第7章《问与答》(spine1264;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1231.html;u117-ch07-022)。
- 结论依据:117前三组问答全文与公式完整实读,保留等价实现和专用函数的理由,纠正把mn模型写成精确倍数的过度解释。
- 原始内容:联合使用set_intersection和set_is_equal操作来达成相同的目的。无论我们按照本章给出的实现方式还是联合使用set_intersection和set_is_equal,它们的时间复杂度都是O(mn),这里m和n分别代表集合S1和S2的成员个数。但是,如果调用set_inters