知识卡片
包含关系由成员归属决定
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)。