算法面试题：贪心算法

1. 贪心算法的核心思想是什么？

• 在每一步选择当前最优解。
• 期望局部最优构成全局最优。
• 需证明贪心策略的正确性。

2. 常见贪心算法题有哪些？

• 活动选择问题。
• 背包问题的贪心近似。
• 最小生成树（Kruskal、Prim）。

3. 贪心算法与动态规划的差异是什么？

• 贪心只考虑局部最优。
• 动态规划考虑所有子问题。
• 贪心更简单但不一定总是正确。

4. 你如何判断是否适合使用贪心？

• 问题具有贪心选择性质。
• 具有最优子结构并且子问题之间独立。

5. 为什么不能用贪心解决所有问题？

• 局部最优不一定能导出全局最优。
• 需要证明算法满足贪心性质。

6. 贪心算法常见的实现技巧是什么？

• 先排序再遍历。
• 使用优先队列维护最优选择。
• 设计合适的贪心准则。

7. 你如何分析贪心算法的复杂度？

• 分析排序、优先队列操作和遍历成本。
• 常见复杂度为 O(n log n)。

8. 面试中如何解释贪心算法的正确性？

• 给出反证法或交换论证。
• 说明为什么不选择其他策略会导致更差结果。