跳转到内容
计算机基础百科
搜索
Ctrl
K
取消
选择主题
深色
浅色
自动
第一卷 · 计算与抽象
第二卷 · 数字逻辑与计算机组成
第三卷 · 数据结构
第四卷 · 算法
第五卷 · 编程语言与编译
第六卷 · 操作系统
第七卷 · 计算机网络
第八卷 · 数据库系统
第九卷 · 分布式系统
第十卷 · 计算理论
第十一卷 · 软件工程与系统设计
第十二卷 · 安全与密码学
术语表
参考文献与延伸阅读
导读
第一部分 · 分析与基础
渐近复杂度与主定理
排序与查找
第二部分 · 设计范式
分治
动态规划
贪心
第三部分 · 图算法
图的基本算法
最短路径
网络流与匹配
第四部分 · 进阶
字符串算法
NP 完全问题与近似算法
选择主题
深色
浅色
自动
第四卷 · 算法
›
第二部分 · 设计范式
›
贪心
贪心
活动选择、Huffman 编码、最小生成树(Kruskal/Prim)、区间调度。本章讲贪心正确性的证明方法(交换论证、拟阵),以及贪心失败的经典反例(0/1 背包、找零)。
本章要点
Section titled “本章要点”
贪心必须证明,不能靠感觉
交换论证是最常用的证明技术
拟阵给出贪心成立的一般条件