算法面试题：复杂度与算法设计

1. 如何判断算法的时间复杂度？

• 分析基本操作的执行次数。
• 关注最坏情况、平均情况和最好情况。
• 常见表示法：O(n)、O(n log n)、O(n^2)。

2. 空间复杂度分为哪几类？

• 额外空间：算法运行所需额外内存。
• 输入空间：原始输入所占空间。
• 通常只分析额外空间。

3. 什么是渐进分析？

• 聚焦于输入规模增长后的表现。
• 忽略常数因子和低阶项。
• 用 Big O 表示上界。

4. 如何选择合适的算法？

• 评估数据规模和资源约束。
• 考虑最坏情况表现与实际输入分布。
• 平衡代码复杂度与性能收益。

5. 有没有稳定与不稳定算法之分？

• 稳定排序保持相等元素的相对顺序。
• 对需要稳定性的场景（如多关键字排序）很重要。

6. 何时使用贪心算法？

• 问题可以通过局部最优解构建全局最优。
• 需要证明贪心策略是安全的。

7. 何时使用分治策略？

• 将大问题拆分为独立的子问题。
• 适用于快速排序、归并排序、二分搜索等。

8. 如何提升算法复用性？

• 提炼抽象数据结构与通用组件。
• 使用模块化函数接口。
• 编写清晰注释，方便后续扩展。