知识卡片

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

包含关系由成员归属决定

理解等级:中级

A是B的子集,表示A的每个成员都属于B,可记A⊆B;这里允许A=B。两个集合相等要求成员完全相同,仅数量相等不够:{1,2,3}与{1,2,4}都含三个成员,却不相等。

数学条件和实现需要分开:成员唯一且使用一致的判等规则时,有限集合数量相等并且A⊆B,可推出A=B。本书定义节使用⊂,后文set_is_subset的实际代码允许相等,因此本卡用⊆消除严格子集符号歧义。

113及02795–02796 set_is_subset若size1>size2返回0,再遍历set1,任一项不在set2就返回0,全部通过返回1。数量较少不是充分条件;空集的循环为空所以被判为任意集合的子集,相等集合也允许。最坏成员扫描形成嵌套成本,提前退出可能更快。

114及02796 set_is_equal先比较size,不等返回0,否则return set_is_subset(set1,set2)。同样多的不同成员集合会被逐项检查排除;若绕过集合接口引入重复或判等不一致,不能再依赖该证明。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      所包含的成员完全一样,则称这两个集合相等。例如,如果S1={1,2,3},S2={1,2,3},以及S3={1,2,4},则S1等于S2,但S1不等于S3。以集合的写法表示为: S1=S2表示S1和S2相等;S1≠S2表示S1和S2不等。 3.如果集合S2包含另一个集合S1所有的成员,则S1是S2的

    • · 查看原书依据

      首先比较它们的成员个数。如果这个测试失败,则set1不是set2的子集。否则,调用list_next来遍历set1中的成员,直到找到一个并不属于集合set2的成员,这说明set1不是set2的子集,或者遍历完整个set1,此时可确定set1是set2的子集。 set_is_subset的时间复杂度为

    • · 查看原书依据

      只需要确定set 1是否为set2的子集就可以返回结果了,这可以通过调用set_is_subset来实现。 set_is_equal的运行时复杂度为O(mn),这里m和n分别代表集合set1和set2中的成员个数。这是因为set_is_subset的复杂度为O(mn)。

    参考来源

    - 位置:《算法精解:C语言描述》第7章《集合的定义》(spine1248;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1215.html;u100-ch07-004)。 - 结论依据:100定义2/3及原例全文实读;113/114实际实现已读,为允许相等和数量筛选条件提供后续来源。 - 原始内容:所包含的成员完全一样,则称这两个集合相等。例如,如果S1={1,2,3},S2={1,2,3},以及S3={1,2,4},则S1等于S2,但S1不等于S3。以集合的写法表示为: S1=S2表示S1和S2相等;S1≠S2表示S1和S2不等。 3.如果集合S2包含另一个集合S1所有的成员,则S1是S2的 - 位置:《算法精解:C语言描述》第7章《set_is_subset》(spine1260;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1227.html;u113-ch07-004)。 - 结论依据:113及02795–02796 set_is_subset若size1>size2返回0,再遍历set1,任一项不在set2就返回0,全部通过返回1。数量较少不是充分条件;空集的循环为空所以被判为任意集合的子集,相等集合也允许。最坏成员扫描形成嵌套成本,提前退出可能更快。 - 原始内容:首先比较它们的成员个数。如果这个测试失败,则set1不是set2的子集。否则,调用list_next来遍历set1中的成员,直到找到一个并不属于集合set2的成员,这说明set1不是set2的子集,或者遍历完整个set1,此时可确定set1是set2的子集。 set_is_subset的时间复杂度为 - 位置:《算法精解:C语言描述》第7章《set_is_equal》(spine1261;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1228.html;u114-ch07-004)。 - 结论依据:114及02796 set_is_equal先比较size,不等返回0,否则return set_is_subset(set1,set2)。同样多的不同成员集合会被逐项检查排除;若绕过集合接口引入重复或判等不一致,不能再依赖该证明。 - 原始内容:只需要确定set 1是否为set2的子集就可以返回结果了,这可以通过调用set_is_subset来实现。 set_is_equal的运行时复杂度为O(mn),这里m和n分别代表集合set1和set2中的成员个数。这是因为set_is_subset的复杂度为O(mn)。