知识卡片
近似质量不等于运行复杂度
近似算法至少要分别讨论结果有多接近最优、需要多少计算。本书称贪心集合覆盖“对数级的复杂度”,不能将它理解为运行时间O(log m)。
补充核验:对可覆盖、每个子集成本相同的集合覆盖,最大新增覆盖贪心法有1+ln m的近似因子上界,m为待覆盖成员数;它约束选中数量与最优数量之比,不是执行步骤数。Dartmouth算法讲义,定理1(2026-11-06读取定义、算法与定理)。
本章链表实现每轮还要为候选子集构造交集,再更新成员。正文O(m³)推导针对候选恰有m个且各只含一个成员的特定规模关系;一般输入还需计入候选数量与各子集大小,不能只凭m就把该推导当统一运行上界。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
对数级的复杂度。该算法的工作原理是:不断从P中选出一个集合,使其能够覆盖S中最多的成员数量。换句话说,该算法每次都尝试尽可能早覆盖S中更多的成员,因此该算法采用了贪心法(见第1章)的思路。由于每个集合都是从P中选出的,如果P被移除,则它的成员也将从S中移除。当P中剩下的成员中没有任何集合能够覆盖S中
参考来源
- 位置:《算法精解:C语言描述》第7章《Set示例:集合覆盖》(spine1263;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1230.html;u116-ch07-019)。
- 结论依据:116近似段与末尾完整复杂度推导实读;对数近似因子由大学课程原始讲义定理1补充核验,不宣称本书证明了该结论,也未测性能。
- 原始内容:对数级的复杂度。该算法的工作原理是:不断从P中选出一个集合,使其能够覆盖S中最多的成员数量。换句话说,该算法每次都尝试尽可能早覆盖S中更多的成员,因此该算法采用了贪心法(见第1章)的思路。由于每个集合都是从P中选出的,如果P被移除,则它的成员也将从S中移除。当P中剩下的成员中没有任何集合能够覆盖S中