算法下界分析（algorithm lower bound analysis），理学-计算机科学技术-计算机科学理论-算法学-算法分析，在近似算法的设计与分析中，近似性能比的分析有时并不紧（tight），即分析得到的近似性能比并不是所设计算法的严格下界，为此需要对算法的下界进行分析。从理论上讲，如果某个问题的某个算法的下界与该问题的理论下界相一致，则该算法的性能是不可改进的，也是最好的，集合覆盖问题的贪心算法就是如此。然而，这种情况是极少发生的。对于没有达到问题理论下界的近似算法，研究其下界的意义在于说明对算法所作分析的严谨性。算法下界分析的方法一般是构造恰好达到所得近似性能比的问题实例。下面给出集合覆盖问题的例子，该实例说明，贪心算法的近似性能比下界为调和级数。集合覆盖问题（见图）一般化描述为：实例：基本元素集合；E的子集的集合，。目标：求的一个标号子集，满足，使最小化。构造的特殊实例如下：含有个元素，每个的子集最多含有个元素。最小子覆盖为，含有个互不相交的元子集。