知识卡片

普通读书笔记卡 · 3725.b.1.u · 生成模型:未记录

等价集合表达式成本可不同

理解等级:中级

同一成员关系可由不同操作组合表达: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