贪心算法 分类: 基础理论贪心算法 定义 在每一步选择局部最优解，期望通过局部最优达到全局近似最优的算法策略 核心要点 每步做出当前看起来最好的选择，不回溯 对子模函数（submodular function）最大化，贪心有 (1−1/e)(1-1/e)(1−1/e) 近似比保证 在子空间重建中，贪心选择残差能量最大的向量等价于逐步最大化子空间覆盖 时间复杂度通常远低于全局搜索（NP-hard 问题的实用替代） 代表工作 ResPrune: 贪心子空间扩展选择视觉 token 相关概念 残差能量 正交投影